Chapter 1c


Graph Theory and Geography


Technical Terms:

adjacency matrix, adjacent, arc, bipartite, circumference, closed walk, complement, complete bipartite graph, complete graph, component, connected, cutnode, cycle, degree, diameter, directed graph (digraph), distance, edge, eulerian, endnode, geodesic, girth, graph, hamiltonian, incident, induced subgraph, isolated node, labeled, length, loop, metric, multigraph, node, open walk, oriented graph, path, planar, pseudograph, regular, spanning subgraph, subgraph, supergraph, theta graph, trail, walk.

Link to Chapter 1.


Basic Material

The basic material presented below follows that of Harary, 1969.

Note: Throughout the rich history of graphs, many names have been used for the same objects. Nodes are also called points or vertices. In this book, V is used for the set of nodes and n is generally used for the number of nodes. Similarly, the words line, edge, and arc have been used interchangeably. This book uses edge for undirected connection and arc for directed connection. The letter E is used for the set of edges (or arcs) and m for the number of edges.

The most common way to represent a graph is by drawing a picture of it in the plane. If this can be done so that all intersections of edges occur at nodes, the graph is called planar. Another way to represent a graph is by its adjacency matrix. If G has n labeled nodes, 1,2, ..., n, the adjacency matrix is an n by n matrix whose entry in row i, column j is 1 if ij is an edge, 0 otherwise. Figure 1c.1 shows a picture of a graph on the left and its corresponding adjacency matrix on the right.

Image

Figure 1c.1. The graph on the left has adjacency matrix on the right.

Connectedness: Terminology

A particularly useful property that a graph can have is that of being connected. The basic structure of connected and disconnected graphs is developed below.

The distance d(u,v) between two nodes u and v in G is the length of a shortest path joining them if any; otherwise we say d(u,v) = ∞ . In a connected graph, distance is a metric; that is, for all nodes u, v, and w,

Degree and Euler's Theorem

The degree of a node vi in graph G, denoted di or deg vi, is the number of edges incident with vi. Since every edge is incident with two nodes, it contributes 2 to the sum of the degrees of the nodes. Thus, Euler's Theorem (the first theorem of graph theory), follows below.

Theorem 1c.1. Euler's Theorem  The sum of the degrees of the nodes of a graph G is twice the number of edges: Σ(deg vi) = 2m.

Corollary 1c.1.1. In any graph, the number of nodes of odd degree is even.

In an (n,m) graph, 0 ≤ deg vn - 1 for every node v. The graph with n nodes, each of degree n - 1, is called the complete graph on n nodes and is denoted Kn. The minimum degree among the nodes of G is denoted min deg G while max deg G is the largest such number. If min deg G = max deg G = r, then all nodes have the same degree and G is called regular of degree r, written deg G = r. The first interesting regular graphs are those of degree 3, called cubic graphs.

Corollary 1c.1.2. Every cubic graph has an even number of nodes.

The cube Q3 is the prime example of a cubic graph. If we denote the square by Q2, we can define an n-cube, Qn, for n≥3 to be the regular graph of degree n with 2n nodes obtained by taking two copies of Qn-1 and joining corresponding edges.

An isolated node has degree zero; an endnode has degree one

Dinner Guests and Ramsey's Theorem

The following puzzle has been a guest at many dinner parties:

Prove that at any party with six people, there are three mutual acquaintances or three mutual non-acquaintances.

Let nodes represent people and adjacency between nodes represent acquaintanceship between people. This puzzle translates to the following theorem.

Theorem 1c.2. Ramsey's Theorem

For any graph G with six nodes, either G or Gc contains a triangle.

Proof: Let v be a node of a graph G with six nodes. Since v is adjacent either in G or in Gc to the other five nodes of G, assume without loss of generality that there are three nodes u1, u2, u3 adjacent to v in G. If any two of these nodes are adjacent, then they are two nodes of a triangle whose third node is v. If no two of them are adjacent in G, then u1, u2, and u3 are the nodes of a triangle in Gc.

Bipartite Graphs and König's Theorem

A bipartite graph G is a graph whose node set V can be partitioned into two subsets V1 and V2 such that every edge of G joins V1 with V2. If G contains every edge joining V1 and V2, then G is a complete bipartite graph (if V1 has m nodes and V2 has n nodes, this graph is denoted Km,n).

Theorem 1c.3 König's Theorem (Theorem 1c.3). A graph is bipartite if and only if all its cycles are even.

Proof: If G is a bipartite graph, then its edge set V can be partitioned into two sets V1 and V2 so that every edge of G joins a node of V1 with a node of V2. Thus, every cycle v1v2 ... vnv1 in G necessarily has its oddly subscripted nodes in V1 (say) and the others in V2, so that its length n is even.

For the converse, assume without loss of generality that G is connected (otherwise, consider the components of G separately). Take any node v1 in V and let V1 consist of v1 and all nodes at even distance from v1, while V2 = V - V1. Since all the cycles of G are even, every edge of G joins a node of V1 with a node of V2. For suppose there is an edge uv joining two nodes of V1. Then the union of geodesics from v1 to v and from v1 to u together with the edge uv contains an odd cycle, a contradiction.

Traversability: Eulerian and Hamiltonian Graphs

The Königsberg bridge problem can be abstracted away from the physical world to the graphical world: given a graph G, is it possible to find a walk that traverses each edge exactly once, goes through all nodes, and ends at the starting node? Any graph for which this property is possible is called eulerian. An eulerian graph has an eulerian trail, a closed trail containing all nodes and edges. An eulerian graph must be connected.

Theorem 1c.4 (Eulerian Characterization Theorem).  The following statements are equivalent for a connected graph G:

  1. G is eulerian.
  2. Every node of G has even degree.
  3. The set of edges of G can be partitioned into cycles.

Proof:

(1) implies (2).

Let T be an eulerian trail in G. Each occurrence of a given node in T contributes 2 to the degree of that node, and since each edge of G appears exactly once in T, every node must have even degree.

(2) implies (3)

Since G is connected and nontrivial, every node has degree at least 2, so G contains a cycle Z. The removal of the edges of Z results in a spanning subgraph G1 in which every node still has even degree. If G1 has no edges, then (3) already holds; otherwise, a repetition of the argument applied to G1 results in a graph G2 in which again all nodes are even. When a totally disconnected graph Gt is obtained, we have a partition of the edges of G into t cycles.

(3) implies (1)

Let Z1 be one of the cycles of this partition. If G consists only of this cycle, then G is clearly eulerian. Otherwise, there is another cycle Z2 with a node v in common with Z1. The walk beginning at v and consisting of the cycles Z1 and Z2 in succession is a closed trail containing the edges of these two cycles. Continuing the process, we can construct a closed trail containing all edges of G; hence G is eulerian.

From this Theorem, it follows that if a connected graph G has no nodes of odd degree, then G has a closed trail containing all the nodes and edges of G (and analogously for connected G with some odd nodes).

Corollary 1c.4.1. Let G be a connected graph with exactly 2n odd nodes, n≥1. Then the set of edges of i can be partitioned into n open trails.

Corollary 1c.4.2. Let G be a connected graph with exactly two odd nodes. Then G has an open trail containing all the nodes and edges of G (which begins at one of the odd nodes and ends at the other).

Eulerian graphs can be characterized in a standard fashion. The graphical version of Hamilton's Around the World Puzzle asks for the construction of a cycle containing every node of a dodecahedron. If a graph G has a spanning cycle Z, then G is called a hamiltonian graph and Z a hamiltonian cycle. It remains a challenging unsolved problem to discover an elegant, useful characterization of hamiltonian graphs, rather than only a paraphrase of the definition. We present below a few conditions that are partial efforts at that characterization.

Since a hamiltonian graph contains a closed trail including each node, removing a single node cannot disconnect a hamiltonian graph. (A node whose removal disconnects a graph is called a cutnode; for more information on cutnodes see Chapter 4c.) Therefore, we have shown the following theorem.

Theorem 1c.5. No hamiltonian graph has a cutnode.

A theta graph looks like the Greek letter theta. The simplest example is shown in Figure 1c.2.

Image

Figure 1c.2. The simplest example of the theta graph is shown here.

In general, a theta graph has 2 nodes of degree 3 (like the red nodes of Figure 1c.2) and 3 disjoint paths joining them (like the 3 colored paths in Figure 1c.2). Clearly any theta graph is non-hamiltonian. It can be shown that if G is non-hamiltonian, connected, and has no cutnodes, then G contains a theta subgraph.

Theorem 1c.6. Hamiltonian Sufficient Condition Theorem (Pósa).  Let G have n nodes, n ≥ 3. If for every t, 1 ≤ t < (n-1)/2, the number of nodes of degree not exceeding t is less than t and if, for odd n, the number of nodes of degree at most (n-1)/2 does not exceed (n-1)/2, then G is hamiltonian.

Proof: Suppose the theorem does not hold and let G be a maximal nonhamiltonian graph with n nodes satisfying the hypothesis of the theorem. The addition of any edge to a graph satisfying the conditions of the theorem produces a graph that also satisfies these conditions. Thus, since the addition of any edge to G results in a hamiltonian graph, any two nonadjacent nodes must be joined by a spanning path.

Show first that every node of degree at least (n-1)/2 is adjacent to every node of degree greater than (n-1)/2. Assume (without loss of generality) that deg v1 ≥(n-1)/2 and deg vn n/2, but v1 and vn are not adjacent. Then there is a spanning path v1 v2 . . . vn connecting v1 and vn. Let the nodes adjacent to v1 be v(i,1), ..., v(i,t) where t = deg v1 and 2 = i1<i2<...<it. Clearly vn cannot be adjacent to any node of G of the form v(i,j)-1, for otherwise there would be a hamiltonian cycle v1 v2 . . . v(i,j)-1 vn vn-1 . . . v(i,j) v1 in G. Now since t ≥(n-1)/2, we have n/2 ≤ deg vnn-1-t < n/2 which is impossible, so v1 and vn must be adjacent.

It follows that if deg v n/2 for all nodes v, then G is hamiltonian (see Dirac's Corollary, below). For the above argument implies that every pair of nodes of G are adjacent, so G is complete. But this is a contradiction since Kn is hamiltonian for all ≥ 3.

Therefore, there is a node v in G with deg v < n/2. Let m be the maximum degree among all such nodes and choose v1 so that deg v1 = m. By hypothesis the number of nodes of degree not exceeding m is at most m < n/2. Thus, there must be more than m nodes having degree greater than m and hence at least n/2. Therefore there is some node, say vn, of degree at least n/2 not adjacent to v1. Since v1 and vn are not adjacent, there is a spanning path v1 v2 . . . vn. As above, we write v(i,1), . . ., v(i,m) as the nodes of G adjacent to v1 and note that vn cannot be adjacent to any of the m nodes v(i,j)-1 for 1 ≤ j m. But since v1 and vn are not adjacent and vn has degree at least n/2, m must be less than (n-1)/2, by the first part of the proof. Thus, by hypothesis, the number of nodes of degree at most m is less than m, and so at least one of the m nodes v(i,j)-1, say v', must have degree at least n/2. We have thus exhibited two nonadjacent nodes vn and v', each having degree at least n/2, a contradiction which completes the proof.

These sufficient conditions are not necessary. One can construct, for example, a cubic graph G that is hamiltonian yet does not satisfy the conditions of the theorem.

Corollary 1c.6.1 (Ore). If n ≥3 and for every pair u and v of nonadjacent nodes, deg u + deg v n, then G is hamiltonian.

Corollary 1c.6.2 (Dirac). If for all nodes v of G, deg v n/2, where n ≥3, then G is hamiltonian.