Graphs are diagrams showing connections or relations between various discrete structures. Graphs are composed of two sets. One set has as its members the distinct elements of the structures, such as the cities in a state. Each element of this set is referred to as a vertex (plural vertices), a point, or a node of the graph. The variety of terminology coming from the many sources of a discipline that has yet to mature. The number of vertices of a graph is called the order of the graph. Let V = {v₁, v₂,…, v_p} represent a set of vertices of order p. The other set indicates the relation present among the vertices and is shown by sets of unordered pairs of vertices. These connections are referred to as edges, lines, and arcs (this last term is usually reserved for directed/one-way connections). The number of edges of a graph is called the size. Let E = {e₁, e₂,…, e_q} represent a set of edges whose size is q. We refer to a graph G as having order p and size q, or as (p, q). Each e_i Î E is a pair (v_l, v_m) indicating that the vertex v_l is related to v_m in a symmetrical fashion; that is the same pair as (v_m, v_l). Graphs are used extensively in computer science as an aid in storing, searching, and in aspects of machine theory.

A graph with its set of vertices and edges, V and E, respectively, is designated by G(V, E), by G(p, q), or by G where no ambiguity exists.

Two vertices, v₁ and v₂ Î V, are said to be adjacent if there is an edge (v₁, v₂) Î E.

If a vertex, v, is the end point of an edge, e, we say that e is incident with v (also, v is incident with e).

The number of edges incident with a vertex, v, is called the degree of v, denoted by deg(v).

A vertex is said to be even or odd as goes its degree.

A vertex incident with no edges is called an isolated point. It has degree zero.

An edge that connects the same point (say from v₁ to v₁) is said to be reflexive and is called a loop.

Multiple edges between two vertices are said to be parallel.

A simple graph does not have any loops or parallel edges.

If we allow for multiple edges and/or reflexivity we have a multigraph.

A directed graph, or digraph, consists of two finite sets: a set V(G) of vertices and a set D(G) of directed edges, where each edge is associated with an ordered pair of vertices.

A complete graph on n vertices, denoted K_n, is a simple graph with n vertices whose set of edges contains exactly one edge for each pair of distinct vertices.

A complete bipartite graph on (m, n) vertices, denoted K_m,n, is a simple graph with two sets of vertices say V and W that satisfy the following properties:

1. There is an edge connecting each vertex in V to each vertex in W.
2. There is no edge connecting any vertex in V to any other vertex in V.
3. There is no edge connecting any vertex in W to any other vertex in W.

A graph H is said to be a subgraph of a graph G if, and only if, every vertex of H is also a vertex in G, every edge in H is also an edge in G, and every edge in H has the same endpoints as in G.

The total degree of G is the sum of the degrees of all the vertices of G.

Listing the individual degrees of each vertex in order is known as the score sequence of a graph.

The complement of a graph G has the same vertices but where there were edges in G there are none in G complement and where there were no edges in G there are edges in G complement.

The sum of the degrees of all the vertices of G(p, q) equals twice the number of edges of G. Specifically, if the vertices of G are v₁, v₂,…, v_p, where p is a positive integer, then the total degree of G = deg(v₁) + deg(v₂) + … + deg(v_p) = 2|E|.

Proof: Let V ={ v₁, v₂,…, v_p}. when computing the sum of the degrees each edge in E is counted twice, once for each of the two vertices incident to the edge. Thus this sum of degrees is twice the number of edges.

In any graph there are an even number of vertices of odd degree.

Proof: The sum of all the degrees of V is even from Theorem 11.1.1. (This sum is 2 times the number of edges, therefore is even.) Let this sum be 2q, where q is the number of edges in E. Let V₀ be the set of even vertices, and V₁ be the set of odd vertices. We are to show that the number of vertices in V₁ is even. Now the sum of the degrees of V₀ is even, since the sum of any number of even numbers is even. Let this sum be 2k. Thus the sum, m, of the degrees of the vertices in V₁ must be

m = 2q – 2k = 2(q – k),

which is even.

Example
Applying the fact that the number of vertices with odd degree is even.

Is there a graph with eleven vertices and score sequence: 1, 1, 2, 2, 2, 3, 4, 4, 4, 6, 8?

Solution: No. Such a graph would have three vertices of odd degree, which is impossible by Proposition 11.1.3.

Alternatively, The sum of the degrees is 37, which is not even so by Theorem 11.1.1 this is not a graph.

Example
For a graph G with n vertices, show that the number of edges in "E union E^c" is n(n – 1)/2.

Proof: Let G be a simple graph with n vertices and edge set E. Each vertex can have at most n - 1 edges. The total degree of a complete graph, K_n ,  with n vertices is n(n - 1). Now the edge set of K_n is just E union E^c. The cardinality of the edge set of K_n is  n(n – 1)/2 by Theorem 11.1.1. Hence the number of edges in E union E^c is n(n – 1)/2. []

Example (problem 11.1 #12)
Consider the wolf (w), goat (g), cabbage (c), ferryman (f) problem. The initial state is  wgcf / (on the left side of the river, /), and the desired final state is /wgcf (all on the right side of the river). The problem is transporting these without letting the wolf eat the goat or the goat eat the cabbage, which each would surely do if not in the presence of the ferryman.

The solution is easily found by a graphical approach. Begin with the initial arrangement wgcf / and draw those arrangements that can be reached that are not arrangements to be avoided. At each stage ask yourself, "Where can I go from here?" and draw those arrangements. Two solutions: