Nine people are at a gathering. Is it possible that each of them shakes hands with exactly three of the others? Try to arrange it and something always goes wrong at the end. The reason is a count. If each of nine people took part in three handshakes, there would be \(9\cdot 3=27\) hands shaken; but every handshake involves two hands, so the number of hands shaken is even. No arrangement exists.
The argument did not care who the people were or where they stood. It used only which pairs were joined. A structure consisting of objects and a set of joined pairs is called a graph, and graphs model road and computer networks, molecules, timetabling conflicts, and the relations of Chapter 2. This chapter introduces the basic vocabulary, proves the main theorem about the simplest connected graphs, the trees, in several equivalent forms, and then characterizes two further classes of graphs by what they do not contain. The proofs draw on everything so far: double counting, induction on the size of a structure, extremal choices justified by well-ordering, and equivalence relations.
6.1 Vertices, edges, and degrees
Definition 6.1 (graph). A graph \(G\) consists of a finite nonempty set \(V\) of vertices and a set \(E\) of edges, where each edge is a two-element subset of \(V\) . An edge \(\{u,v\}\) is written \(uv\) ; its endpoints \(u\) and \(v\) are adjacent, and are neighbours of each other. The degree \(\deg(v)\) of a vertex \(v\) is the number of edges that contain \(v\) .
By this definition an edge joins two different vertices, and two vertices are joined by at most one edge; such graphs are sometimes called simple. A graph is not a picture. A drawing with dots and lines is one of many ways to present a graph, and two very different drawings may show the same graph. What defines the graph is the pair of sets \(V\) and \(E\) .
Several families of graphs have standard names. The complete graph \(K_n\) has \(n\) vertices and all \(\binom n2\) possible edges. The path \(P_n\) has vertices \(v_1,\dots,v_n\) and edges \(v_iv_{i+1}\) . The cycle \(C_n\) , for \(n\ge 3\) , is the path \(P_n\) with the additional edge \(v_nv_1\) . The complete bipartite graph \(K_{m,n}\) has \(m+n\) vertices in two groups of sizes \(m\) and \(n\) , with an edge between every two vertices in different groups and no edge inside a group. A graph \(H\) is a subgraph of \(G\) if its vertices are vertices of \(G\) and its edges are edges of \(G\) .
Theorem 6.2 (handshake lemma). In every graph, the sum of the degrees of the vertices is twice the number of edges:
Proof. Count the pairs \((v,e)\) in which \(v\) is a vertex and \(e\) is an edge containing \(v\) . Sorting the pairs by their vertex, each vertex \(v\) occurs in \(\deg(v)\) pairs, so the number of pairs is the sum of the degrees. Sorting the pairs by their edge, each edge occurs in exactly \(2\) pairs, one for each endpoint, so the number of pairs is \(2\lvert E\rvert\) .
Corollary 6.3 (odd vertices come in pairs). In every graph the number of vertices of odd degree is even.
Proof. The sum of all degrees is even. Removing the even degrees from the sum leaves an even number, which is the sum of the odd degrees; and a sum of odd numbers is even only if there is an even number of them.
The corollary settles the opening question: a graph with nine vertices of degree \(3\) would have an odd number of odd-degree vertices.
Example 6.1: Which lists of degrees can occur?
The list \(3,3,3,3,3,3,3,3,3\) . The sum is \(27\) , which is odd. By the handshake lemma no graph has these degrees.
The list \(3,3,2,2,1,1\) . The sum is \(12\) , so a graph with these degrees would have \(6\) edges. One exists: on the vertices \(a,b,c,d,e,f\) take the edges \(ab\) , \(ac\) , \(ae\) , \(bd\) , \(bf\) , \(cd\) . Then \(a\) and \(b\) have degree \(3\) , \(c\) and \(d\) have degree \(2\) , and \(e\) and \(f\) have degree \(1\) .
The list \(4,4,4,1,1\) . The sum is \(14\) , which is even, so parity raises no objection. Still no graph has these degrees. In a graph with five vertices a vertex of degree \(4\) is adjacent to all four of the others. If three vertices have degree \(4\) , then each of the remaining two is adjacent to all three of them and has degree at least \(3\) , not \(1\) .
So the parity condition is necessary and not sufficient. This pattern, in which a simple count rules out some cases and a structural argument is needed for the rest, recurs throughout the chapter. Since a graph on five named vertices is a choice of which of the \(\binom 52=10\) possible edges to include, there are only \(2^{10}=1024\) such graphs, and checking all of them confirms that none has the degree list \(4,4,4,1,1\) .
6.2 When two graphs are the same
Two graphs on different vertex sets cannot be equal, but they can have identical structure.
Definition 6.4 (isomorphism). An isomorphism from a graph \(G\) to a graph \(H\) is a bijection \(f\) from the vertex set of \(G\) to the vertex set of \(H\) such that, for all vertices \(u\) and \(v\) of \(G\) , \(uv\) is an edge of \(G\) if and only if \(f(u)f(v)\) is an edge of \(H\) . If an isomorphism exists, \(G\) and \(H\) are isomorphic.
An isomorphism is a renaming of the vertices that carries edges to edges and non-edges to non-edges. A property of graphs that is shared by all graphs isomorphic to a graph having it is called an invariant: the number of vertices, the number of edges, the list of degrees in decreasing order, the presence of a triangle. The word is used here for properties preserved under renaming, not under the moves of a process as in Chapter 3, but the logic of its use is the same.
That logic is asymmetric. To prove that two graphs are isomorphic, exhibit a bijection and check every edge. To prove that they are not, exhibit one invariant on which they differ. Agreement on several invariants proves nothing.
Example 6.2: Same degrees, different graphs
Consider three graphs, each with six vertices.
The graph \(G_1\) has vertices \(a_1,a_2,a_3,b_1,b_2,b_3\) and nine edges: the triangle \(a_1a_2\) , \(a_2a_3\) , \(a_1a_3\) ; the triangle \(b_1b_2\) , \(b_2b_3\) , \(b_1b_3\) ; and the three edges \(a_1b_1\) , \(a_2b_2\) , \(a_3b_3\) . The graph \(G_2\) has vertices \(h_0,\dots,h_5\) and nine edges: the hexagon \(h_0h_1\) , \(h_1h_2\) , \(h_2h_3\) , \(h_3h_4\) , \(h_4h_5\) , \(h_5h_0\) and the chords \(h_0h_3\) , \(h_1h_5\) , \(h_2h_4\) . The graph \(G_3\) has vertices \(k_0,\dots,k_5\) , the hexagon \(k_0k_1,\dots,k_5k_0\) , and the chords \(k_0k_3\) , \(k_1k_4\) , \(k_2k_5\) . In all three graphs every vertex has degree \(3\) .
\(G_1\) and \(G_2\) are isomorphic. Define \(f\) by
The nine edges of \(G_1\) go to \(h_0h_1\) , \(h_1h_5\) , \(h_0h_5\) , then \(h_3h_2\) , \(h_2h_4\) , \(h_3h_4\) , then \(h_0h_3\) , \(h_1h_2\) , \(h_5h_4\) . These are nine different edges of \(G_2\) , and \(G_2\) has only nine, so \(f\) carries the edge set of \(G_1\) onto that of \(G_2\) ; hence non-edges go to non-edges as well.
\(G_1\) and \(G_3\) are not isomorphic. The graph \(G_1\) contains a triangle. In \(G_3\) every edge joins a vertex with even index to a vertex with odd index: the hexagon edges join consecutive indices, and each chord joins indices differing by \(3\) . Three vertices that are pairwise adjacent would need three indices of pairwise different parity, which is impossible. So \(G_3\) contains no triangle, and containing a triangle is an invariant.
Exhaustive search over all \(6!=720\) bijections agrees: exactly \(12\) of them are isomorphisms from \(G_1\) to \(G_2\) , and none is an isomorphism from \(G_1\) to \(G_3\) . The search is feasible for six vertices and hopeless for sixty, where the number of bijections has \(82\) digits; the invariant argument works at any size.
6.3 Walks, paths, and connectedness
Definition 6.5 (walk, path, cycle, connected). A walk in a graph is a sequence of vertices \(v_0,v_1,\dots,v_k\) in which each consecutive pair \(v_{i-1}v_i\) is an edge; its length is \(k\) , the number of edges traversed, and it is a walk from \(v_0\) to \(v_k\) . A path is a walk whose vertices are all different. A walk is closed if \(v_0=v_k\) . A cycle is a closed walk of length at least \(3\) whose vertices \(v_0,\dots,v_{k-1}\) are all different. A graph is connected if for every two vertices \(u\) and \(v\) there is a walk from \(u\) to \(v\) .
A single vertex is a walk, and a path, of length \(0\) . A walk may repeat vertices and edges; a path may not.
Lemma 6.6 (walks contain paths). If there is a walk from \(u\) to \(v\) , then there is a path from \(u\) to \(v\) .
Proof. The set of lengths of walks from \(u\) to \(v\) is a nonempty set of natural numbers; by the well-ordering principle choose a walk \(v_0,\dots,v_k\) from \(u\) to \(v\) of least length. If some vertex occurred twice, say \(v_i=v_j\) with \(i<j\) , then \(v_0,\dots,v_i,v_{j+1},\dots,v_k\) would be a shorter walk from \(u\) to \(v\) . So all its vertices are different and it is a path.
Proposition 6.7 (components). In any graph, the relation “there is a walk from \(u\) to \(v\) ” is an equivalence relation on the vertex set.
Proof. Reflexive: the walk of length \(0\) at \(u\) . Symmetric: a walk from \(u\) to \(v\) read backwards is a walk from \(v\) to \(u\) , because edges have no direction. Transitive: a walk from \(u\) to \(v\) followed by a walk from \(v\) to \(w\) is a walk from \(u\) to \(w\) .
The equivalence classes are the vertex sets of the connected components of the graph: each class, with all the edges of the graph between its vertices, is a connected graph, and no edge joins two different classes. By Theorem 2.17 the components partition the vertices. A graph is connected exactly when it has one component.
How few edges can a connected graph have?
Theorem 6.8 (edges and components). A graph with \(n\) vertices and \(m\) edges has at least \(n-m\) connected components. In particular a connected graph with \(n\) vertices has at least \(n-1\) edges.
Proof. By induction on \(m\) . A graph with no edges has \(n\) components, each a single vertex. Let \(m\ge 0\) , assume the claim for graphs with \(m\) edges, and let \(G\) be a graph with \(n\) vertices and \(m+1\) edges. Remove one edge \(e=uv\) to obtain a graph \(G'\) with \(m\) edges, which has at least \(n-m\) components by the induction hypothesis. Restoring \(e\) changes the components in one of two ways. If \(u\) and \(v\) lie in the same component of \(G'\) , the components are unchanged. If they lie in different components, those two merge into one and the others are unchanged. Either way \(G\) has at least \((n-m)-1=n-(m+1)\) components. The last sentence of the theorem is the case of one component: \(1\ge n-m\) .
Notice the direction of the inductive step. It began with an arbitrary graph having \(m+1\) edges and removed an edge to reach a smaller graph. It did not begin with a smaller graph and add an edge.
6.4 Trees
A connected graph with \(n\) vertices needs at least \(n-1\) edges. The connected graphs that use no more than they need form the most important class of graphs.
Definition 6.9 (tree, forest, leaf). A tree is a connected graph that contains no cycle. A graph with no cycle, connected or not, is a forest. A vertex of degree \(1\) is a leaf.
Lemma 6.10 (trees have leaves). Every tree with at least two vertices has at least two leaves.
Proof. Let \(T\) be a tree with at least two vertices. Among all paths in \(T\) choose one of greatest length, \(v_0,v_1,\dots,v_k\) ; there are finitely many paths, and \(k\ge 1\) because \(T\) is connected and has two vertices. We show that \(v_0\) is a leaf. It is adjacent to \(v_1\) . Suppose it had another neighbour \(w\) . If \(w\) is not on the path, then \(w,v_0,v_1,\dots,v_k\) is a longer path, contradicting the choice. If \(w=v_i\) for some \(i\ge 2\) , then \(v_0,v_1,\dots,v_i,v_0\) is a cycle, contradicting the definition of a tree. So \(\deg(v_0)=1\) . The same argument applies to \(v_k\) , and \(v_k\ne v_0\) .
Lemma 6.11 (removing a leaf). If \(v\) is a leaf of a tree \(T\) with at least two vertices, then removing \(v\) and its edge from \(T\) leaves a tree.
Proof. The smaller graph has no cycle, since a cycle in it would be a cycle in \(T\) . It is connected: for two of its vertices \(x\) and \(y\) there is a path from \(x\) to \(y\) in \(T\) by Lemma 6.6, and this path does not pass through \(v\) , because a vertex in the interior of a path has two different neighbours on the path and \(v\) has only one neighbour.
Theorem 6.12 (edges of a tree). A tree with \(n\) vertices has exactly \(n-1\) edges.
Proof. By induction on \(n\) . A tree with one vertex has no edges. Let \(n\ge 1\) , assume the claim for trees with \(n\) vertices, and let \(T\) be a tree with \(n+1\) vertices. By Lemma 6.10, \(T\) has a leaf \(v\) , and by Lemma 6.11 removing \(v\) leaves a tree with \(n\) vertices, which has \(n-1\) edges by the induction hypothesis. Restoring \(v\) restores one edge, so \(T\) has \(n\) edges.
One more lemma prepares the main theorem.
Lemma 6.13 (edges on cycles are dispensable). If \(G\) is connected and \(e\) is an edge of a cycle of \(G\) , then the graph obtained from \(G\) by removing the edge \(e\) is still connected.
Proof. Let \(e=xy\) . The rest of the cycle is a path from \(x\) to \(y\) that does not use \(e\) . In any walk of \(G\) , each traversal of \(e\) can be replaced by that path, traversed in the appropriate direction. So any two vertices joined by a walk in \(G\) are joined by a walk that avoids \(e\) .
Theorem 6.14 (characterizations of trees). For a graph \(G\) with \(n\) vertices, the following statements are equivalent.
(a) \(G\) is a tree: connected, with no cycle.
(b) \(G\) is connected and has exactly \(n-1\) edges.
(c) \(G\) has no cycle and has exactly \(n-1\) edges.
(d) For every two vertices \(u\) and \(v\) of \(G\) there is exactly one path from \(u\) to \(v\) .
Proof. (a) implies (b) and (c). This is Theorem 6.12.
(b) implies (a). Suppose \(G\) is connected with \(n-1\) edges and, for contradiction, contains a cycle. By Lemma 6.13, removing an edge of the cycle leaves a connected graph with \(n\) vertices and \(n-2\) edges, contradicting Theorem 6.8.
(c) implies (a). Suppose \(G\) has no cycle and has \(n-1\) edges, and let its components have \(n_1,\dots,n_c\) vertices. Each component is connected and has no cycle, so it is a tree and has \(n_i-1\) edges by Theorem 6.12. Adding up, \(G\) has \(n-c\) edges. Hence \(n-c=n-1\) , so \(c=1\) and \(G\) is connected.
(a) implies (d). Let \(G\) be a tree. Since \(G\) is connected, Lemma 6.6 gives at least one path between any two vertices. Suppose \(P\) and \(Q\) are two different paths from \(u\) to \(v\) . A path starting at \(u\) can be recovered from its set of edges, by taking the one edge of the set at \(u\) , then the other edge of the set at the vertex reached, and so on; so \(P\) and \(Q\) do not have the same set of edges, and one of them, say \(P\) , has an edge \(e\) that is not an edge of \(Q\) . Name the endpoints of \(e\) so that \(e=xy\) with \(x\) coming before \(y\) when \(P\) is traversed from \(u\) to \(v\) . A path passes through each of its edges only once, so the part of \(P\) from \(u\) to \(x\) and the part of \(P\) from \(y\) to \(v\) do not use \(e\) . Follow \(P\) backwards from \(x\) to \(u\) , then \(Q\) from \(u\) to \(v\) , then \(P\) backwards from \(v\) to \(y\) . This is a walk from \(x\) to \(y\) in the graph \(G'\) obtained from \(G\) by removing the edge \(e\) . Lemma 6.6, applied to \(G'\) and not to \(G\) , gives a path from \(x\) to \(y\) in \(G'\) , that is, a path of \(G\) that does not use \(e\) . Since \(x\) and \(y\) are not adjacent in \(G'\) , this path has length at least \(2\) , and together with \(e\) it forms a cycle in \(G\) . That contradicts (a).
(d) implies (a). If (d) holds then \(G\) is connected. If \(G\) contained a cycle \(v_0,v_1,\dots,v_{k-1},v_0\) , then \(v_0,v_1\) and \(v_0,v_{k-1},v_{k-2},\dots,v_1\) would be two different paths from \(v_0\) to \(v_1\) .
The theorem says that of the three properties “connected”, “no cycle”, and “exactly \(n-1\) edges”, any two imply the third. No single one suffices, and in particular the edge count alone does not: a triangle together with an isolated vertex has \(4\) vertices and \(3\) edges and is neither connected nor free of cycles.
Theorem 6.15 (spanning trees). Every connected graph \(G\) has a spanning tree: a subgraph that is a tree and contains every vertex of \(G\) .
Proof. Consider the process that, as long as the current graph contains a cycle, removes one edge of some cycle. The number of edges is a monovariant, so the process stops. By Lemma 6.13 the property “connected, with the same vertices as \(G\) ” is an invariant. When the process stops the graph has no cycle and is connected, so it is a tree containing every vertex of \(G\) .
Example 6.3: Counting the trees on a few named vertices
How many trees are there with vertex set \(\{1,2,3,4\}\) ? By Theorem 6.14 a tree on four vertices has three edges, and up to isomorphism there are two shapes: the path \(P_4\) and the star, in which one vertex is adjacent to the other three. A path is determined by the order of its vertices, and each path arises from two orders, one the reverse of the other, so there are \(4!/2=12\) paths. A star is determined by its centre, so there are \(4\) stars. In all there are \(12+4=16\) trees.
This can be checked from the other side. There are \(\binom 42=6\) possible edges and \(\binom 63=20\) ways to choose three of them. A set of three edges fails to be a tree exactly when it has a cycle, and with three edges that means it is one of the \(4\) triangles. So \(20-4=16\) sets of three edges form trees, in agreement.
Carrying out the same count by exhaustive enumeration for larger vertex sets gives \(125\) trees on five named vertices and \(1296\) on six. The numbers \(16\) , \(125\) , \(1296\) are \(4^{2}\) , \(5^{3}\) , \(6^{4}\) , instances of Cayley’s formula: there are \(n^{n-2}\) trees on \(n\) named vertices. We do not prove the formula here. Up to isomorphism the counts are far smaller: \(2\) trees on four vertices, \(3\) on five, and \(6\) on six.
Example 6.4: A spanning tree found level by level
The proof of Theorem 6.15 removes edges. A more useful method builds a spanning tree outward from a chosen vertex, the root. Take the graph with vertices \(1,\dots,9\) and the twelve edges
Start with the root \(1\) at level \(0\) . Level \(1\) consists of the neighbours of \(1\) , namely \(2\) and \(3\) . Level \(2\) consists of the vertices not yet reached that are adjacent to a vertex of level \(1\) : these are \(4\) , \(5\) , and \(6\) . Level \(3\) is \(\{7,8\}\) and level \(4\) is \(\{9\}\) . Each vertex other than the root is joined to one neighbour in the previous level, its parent; when there is a choice, take the neighbour with the smallest label. The parent edges are
There are \(8\) of them, they reach all \(9\) vertices, and every vertex is joined to the root through its chain of parents. A connected graph with \(9\) vertices and \(8\) edges is a tree by Theorem 6.14(b). The remaining four edges, \(35\) , \(57\) , \(68\) , and \(89\) , are not in the tree. The method is called breadth-first search, and the level of a vertex is the length of a shortest path to it from the root.
Trees are where a tempting but invalid form of induction is most often seen.
Example 6.5: An induction that builds up
False claim. Every graph in which each vertex has degree at least \(1\) is connected.
Argument. “By induction on the number \(n\) of vertices. Base case \(n=2\) : the graph is a single edge, which is connected. Step: take a connected graph with \(k\) vertices in which every vertex has degree at least \(1\) , and add a new vertex. For the new vertex to have degree at least \(1\) it must be joined to an old vertex, so the new graph is connected, and all its degrees are at least \(1\) .”
Diagnosis. The claim is false: two disjoint edges form a graph on four vertices with all degrees equal to \(1\) and with two components. The step proves something true, that adding a vertex with at least one edge to a connected graph gives a connected graph. But the inductive step for \(P(k+1)\) must treat every graph with \(k+1\) vertices that satisfies the hypothesis, and the argument treats only those obtained by adding a vertex to a smaller graph that satisfies the hypothesis. The graph of two disjoint edges is not obtained that way: removing any of its vertices leaves a vertex of degree \(0\) .
Among the \(64\) graphs on four named vertices, \(41\) have all degrees at least \(1\) , and exactly \(3\) of those are disconnected: the three ways of pairing the vertices into two disjoint edges.
The remedy is the discipline followed in the proofs of Theorems 6.8 and 6.12. Start with an arbitrary object of size \(k+1\) , remove something to reach size \(k\) , apply the hypothesis, and restore what was removed. For trees, the fact that makes removal possible is Lemma 6.10: there is always a leaf to remove.
6.5 Bipartite graphs and colourings
Definition 6.16 (bipartite graph, colouring). A graph is bipartite if its vertex set can be divided into two disjoint sets \(X\) and \(Y\) such that every edge has one endpoint in \(X\) and one in \(Y\) . A proper colouring of a graph with \(k\) colours is a function from the vertices to a set of \(k\) colours such that adjacent vertices receive different colours. The chromatic number \(\chi(G)\) is the least \(k\) for which a proper colouring with \(k\) colours exists.
A graph is bipartite exactly when it has a proper colouring with two colours. The graph \(G_3\) of Example 6.2 is bipartite, with \(X\) the vertices of even index.
Which graphs are bipartite? A triangle is not: three mutually adjacent vertices need three colours. Neither is any cycle of odd length. The theorem says that odd cycles are the only obstruction.
Lemma 6.17 (odd closed walks). If a graph has a closed walk of odd length, then it has a cycle of odd length.
Proof. By strong induction on the length \(k\) of the closed walk \(v_0,v_1,\dots,v_k=v_0\) . No closed walk has length \(1\) , since an edge joins two different vertices; so the smallest odd length is \(3\) , and a closed walk of length \(3\) is a triangle. Let \(k\ge 5\) be odd and assume the claim for all shorter odd lengths. If \(v_0,\dots,v_{k-1}\) are all different, the walk is itself a cycle. Otherwise \(v_i=v_j\) for some \(0\le i<j\le k-1\) . Then \(v_i,v_{i+1},\dots,v_j\) is a closed walk of length \(j-i\) , and \(v_0,\dots,v_i,v_{j+1},\dots,v_k\) is a closed walk of length \(k-(j-i)\) . The two lengths are positive, smaller than \(k\) , and add up to the odd number \(k\) , so one of them is odd, and the induction hypothesis applies to that walk.
Theorem 6.18 (bipartite graphs). A graph is bipartite if and only if it contains no cycle of odd length.
Proof. Suppose \(G\) is bipartite with parts \(X\) and \(Y\) , and let \(v_0,v_1,\dots,v_k=v_0\) be a cycle. Each edge leads from one part to the other, so the vertices alternate between \(X\) and \(Y\) , and returning to the starting part requires an even number of steps. So \(k\) is even.
Conversely, suppose \(G\) has no odd cycle. It is enough to colour each connected component separately, so assume \(G\) is connected, and fix a vertex \(r\) . For each vertex \(v\) let \(d(v)\) be the least length of a walk from \(r\) to \(v\) . Let \(X\) be the set of vertices with \(d(v)\) even and \(Y\) the set with \(d(v)\) odd. Suppose, for contradiction, that some edge \(uv\) has both endpoints in the same set, so that \(d(u)\) and \(d(v)\) have the same parity. A shortest walk from \(r\) to \(u\) , followed by the edge \(uv\) , followed by a shortest walk from \(v\) back to \(r\) , is a closed walk of length \(d(u)+1+d(v)\) , which is odd. By Lemma 6.17, \(G\) has an odd cycle, contrary to hypothesis. So every edge joins \(X\) to \(Y\) .
Corollary 6.19 (trees are bipartite). Every tree is bipartite.
Proof. A tree contains no cycle at all, and in particular no odd cycle.
The theorem is of a kind worth recognising. It gives, for each answer to the question “is this graph bipartite?”, a short piece of evidence that anyone can check. If the answer is yes, the evidence is a colouring. If the answer is no, the evidence is an odd cycle. Chapter 8 returns to such pairs of certificates.
Example 6.6: Colouring by levels
The proof of Theorem 6.18 is an algorithm, and Figure 6.2 shows it running. In the graph of Example 6.4 the levels found by breadth-first search from the root \(1\) are the distances \(d(v)\) . Put \(X=\{1,4,5,6,9\}\) , the vertices on even levels, and \(Y=\{2,3,7,8\}\) , those on odd levels. Each of the twelve edges joins two consecutive levels, hence joins \(X\) to \(Y\) : the graph is bipartite, and the colouring is the evidence.
Now add the edge \(45\) . Both endpoints are on level \(2\) , so this edge lies inside \(X\) . Following the proof, a shortest walk from \(1\) to \(4\) is \(1,2,4\) and a shortest walk from \(5\) back to \(1\) is \(5,2,1\) ; with the edge \(45\) they form the closed walk \(1,2,4,5,2,1\) of length \(5\) . It is not a cycle, since the vertex \(2\) repeats; splitting it there as in Lemma 6.17 gives the closed walk \(2,4,5,2\) of length \(3\) and the closed walk \(1,2,1\) of length \(2\) . The odd one is the triangle on \(2\) , \(4\) , \(5\) . The enlarged graph is not bipartite, and the triangle is the evidence.
For more than two colours no such clean theorem is known, and finding the chromatic number of a large graph is a hard computational problem. A simple upper bound is nevertheless available.
Proposition 6.20 (greedy bound). If every vertex of \(G\) has degree at most \(\Delta\) , then \(\chi(G)\le\Delta+1\) .
Proof. By induction on the number of vertices, with \(\Delta\) fixed. A graph with one vertex needs one colour. Let \(G\) have \(n+1\) vertices, all of degree at most \(\Delta\) , and remove a vertex \(v\) with its edges. The smaller graph still has all degrees at most \(\Delta\) , so by the induction hypothesis it has a proper colouring with \(\Delta+1\) colours. The vertex \(v\) has at most \(\Delta\) neighbours, which use at most \(\Delta\) of the colours, so some colour is unused among them; give it to \(v\) .
Example 6.7: A timetable as a colouring
Seven courses, \(A\) to \(G\) , need examination slots. Two courses cannot share a slot if some student takes both, and the pairs with a common student are
Make a graph with the courses as vertices and these nine pairs as edges. An assignment of slots is a proper colouring, and the least number of slots is the chromatic number.
Three slots suffice. Put \(A\) , \(D\) , \(G\) in the first slot, \(B\) , \(E\) , \(F\) in the second, and \(C\) in the third. No edge joins two courses in the same slot: among \(A\) , \(D\) , \(G\) there are no edges, and among \(B\) , \(E\) , \(F\) there are none.
Two slots do not. The courses \(A\) , \(B\) , \(C\) are pairwise in conflict, a triangle, and need three different slots.
So \(\chi=3\)
, and the argument has the two-sided form of a complete answer: a colouring shows that three slots are enough, and a triangle shows that fewer are not. The largest degree in this graph is \(3\)
, so Proposition 6.20 guarantees only four slots; the bound is not always attained. Choosing the best timetable among many feasible ones, with room sizes and preferences, is a problem of optimization over a discrete structure, and it is taken up in Discrete Optimization, together with shortest paths, matchings, and flows in networks (math.discrete-optimization.shortest-path-flow).
6.6 Traversing every edge once
The oldest theorem of graph theory answers a question about walks. In 1736 Euler was asked whether one could walk through the city of Königsberg crossing each of its seven bridges exactly once and return to the start.
Definition 6.21 (Euler circuit). A trail is a walk that uses no edge more than once. An Euler circuit of a graph is a closed trail that uses every edge of the graph.
Theorem 6.22 (Euler). A connected graph has an Euler circuit if and only if every vertex has even degree.
Proof. Suppose \(G\) has an Euler circuit, and follow it once around. Each time the circuit passes through a vertex \(v\) it uses two edges at \(v\) , one to arrive and one to leave; the start of the circuit is paired with its end in the same way. Every edge at \(v\) is used exactly once, so the edges at \(v\) are divided into pairs and \(\deg(v)\) is even.
Conversely, suppose \(G\) is connected with all degrees even, and let \(W=v_0,v_1,\dots,v_k\) be a trail of greatest possible length; one exists because a trail has at most \(\lvert E\rvert\) edges.
\(W\) is closed. Suppose \(v_k\ne v_0\) . Each passage of \(W\) through \(v_k\) before the end uses two edges at \(v_k\) , and the final arrival uses one more, so \(W\) uses an odd number of the edges at \(v_k\) . Since \(\deg(v_k)\) is even, some edge at \(v_k\) is unused, and \(W\) can be extended along it, contradicting the choice of \(W\) .
\(W\) uses every edge. Suppose some edge is not used by \(W\) . We claim that some unused edge has an endpoint on \(W\) . Take any unused edge \(xy\) . If \(x\) is on \(W\) we are done. Otherwise, since \(G\) is connected there is a path from \(v_0\) to \(x\) ; it starts on \(W\) and ends off \(W\) , so it has a first edge that leaves the vertices of \(W\) , and that edge is unused and has an endpoint on \(W\) . So let \(v_iw\) be an unused edge. Because \(W\) is closed, it can be traversed starting from \(v_i\) : the walk \(w,v_i,v_{i+1},\dots,v_k=v_0,v_1,\dots,v_i\) is a trail with one more edge than \(W\) . This contradicts the choice of \(W\) .
Hence \(W\) is a closed trail using every edge.
In Königsberg the four land masses were joined by bridges in such a way that all four had an odd number of bridges, so no such walk exists. The map of Königsberg has two bridges between some pairs of land masses, which Definition 6.1 does not permit; the theorem and its proof remain valid when several edges may join the same two vertices.
Example 6.8: Complete graphs
In \(K_5\) every vertex has degree \(4\) , so an Euler circuit exists. Here is one:
It first goes round the pentagon, using the edges \(12\) , \(23\) , \(34\) , \(45\) , \(51\) , and then round the five-pointed star, using \(13\) , \(35\) , \(52\) , \(24\) , \(41\) . These are ten different edges, and \(K_5\) has \(\binom 52=10\) edges, so every edge is used exactly once.
In \(K_4\) every vertex has degree \(3\) , so there is no Euler circuit. In general each vertex of \(K_n\) has degree \(n-1\) , so \(K_n\) has an Euler circuit exactly when \(n\) is odd.
Euler’s theorem has the same two-sided shape as Theorem 6.18: a circuit proves that one exists, and a single vertex of odd degree proves that none does. Compare the neighbouring question of whether a graph has a cycle passing through every vertex exactly once. No comparable criterion is known for it, and that contrast, between problems with short certificates on both sides and problems that seem to have them on one side only, is one of the organizing themes of Discrete Optimization (math.discrete-optimization.models-complexity).
Trees will return in the next chapter in a different role. When a problem of size \(n\) is solved by splitting it into smaller problems of the same kind, the pattern of splitting is a tree, and the cost of the method is found by adding up the work at every vertex of that tree. A question to carry forward: if a tree has a root with two children, each of which has two children, and so on for \(k\) levels, how many leaves does it have, and how does \(k\) compare with the number of leaves?
Exercises
-
Use the handshake lemma to find the number of edges of \(K_7\) , of \(K_{3,4}\) , and of the cube graph \(Q_4\) , whose vertices are the \(16\) bit strings of length \(4\) , two being adjacent when they differ in exactly one position.
Answer
\(K_7\) : seven vertices of degree \(6\) , so \(\frac{7\cdot 6}{2}=21\) edges. \(K_{3,4}\) : three vertices of degree \(4\) and four of degree \(3\) , degree sum \(24\) , so \(12\) edges. \(Q_4\) : sixteen vertices of degree \(4\) , degree sum \(64\) , so \(32\) edges.
-
For each list decide whether a graph with those degrees exists, giving a graph or a proof that there is none: (a) \(5,4,3,2,2,1\) ; (b) \(3,3,3,3,2,2\) ; (c) \(5,5,4,3,2,1\) ; (d) \(2,2,2,2,2,2,2\) .
Solution
(a) The sum \(5+4+3+2+2+1=17\) is odd, so by the handshake lemma no such graph exists.
(b) A graph exists. Take a hexagon \(v_1v_2v_3v_4v_5v_6\) and add the chords \(v_1v_4\) and \(v_2v_5\) . The vertices \(v_1,v_2,v_4,v_5\) have degree \(3\) and \(v_3,v_6\) have degree \(2\) .
(c) The sum is \(20\) , which is even, but no graph exists. The list has six entries, so the graph would have six vertices, and a vertex of degree \(5\) is adjacent to all five others. Two vertices of degree \(5\) are both adjacent to each of the remaining four vertices, so every remaining vertex has degree at least \(2\) . The list contains a \(1\) , which is impossible.
(d) The cycle \(C_7\) has seven vertices, each of degree \(2\) .
-
Let \(G\) be a graph with \(n\) vertices in which every vertex has degree at least \(\frac{n-1}{2}\) . Prove that \(G\) is connected, by counting the vertices in the components of two non-adjacent vertices.
Solution
If every two vertices are adjacent, \(G\) is certainly connected. Otherwise let \(u\) and \(v\) be non-adjacent vertices; we show that they lie in the same component, which together with the fact that adjacent vertices lie in the same component shows that \(G\) has only one component.
The component of \(u\) contains \(u\) and all its neighbours, so it has at least \(1+\frac{n-1}{2}\) vertices. The same holds for the component of \(v\) . If the two components were different they would be disjoint, by Proposition 6.7, and \(G\) would have at least
\[ 2\Bigl(1+\frac{n-1}{2}\Bigr)=n+1 \]vertices, which is more than \(n\) . So \(u\) and \(v\) lie in the same component.
-
The complement of a graph \(G\) has the same vertices, and two vertices are adjacent in it exactly when they are not adjacent in \(G\) . Show that \(C_5\) is isomorphic to its complement by giving an explicit isomorphism. Then prove that if a graph with \(n\) vertices is isomorphic to its complement, \(n\) leaves remainder \(0\) or \(1\) on division by \(4\) .
Solution
Label the vertices of \(C_5\) as \(0,1,2,3,4\) , with \(i\) adjacent to \(i+1\) modulo \(5\) . In the complement, \(i\) is adjacent to \(j\) exactly when \(j\equiv i\pm 2\pmod 5\) . Define \(f(i)=2i\bmod 5\) , so that \(f\) sends \(0,1,2,3,4\) to \(0,2,4,1,3\) ; it is a bijection because \(2\) is invertible modulo \(5\) . An edge \(\{i,i+1\}\) of \(C_5\) goes to \(\{2i,2i+2\}\) , whose members differ by \(2\) modulo \(5\) : an edge of the complement. The five edges of \(C_5\) go to five different edges of the complement, which has \(\binom 52-5=5\) edges, so edges correspond to edges and non-edges to non-edges. Hence \(f\) is an isomorphism.
For the second part, suppose a graph with \(n\) vertices and \(m\) edges is isomorphic to its complement. The number of edges is an invariant, so the complement also has \(m\) edges, and together they account for all \(\binom n2\) pairs: \(2m=\frac{n(n-1)}{2}\) , that is, \(n(n-1)=4m\) . Of the consecutive integers \(n\) and \(n-1\) one is odd, so \(4\) must divide the other. Thus \(n\equiv 0\) or \(n\equiv 1\pmod 4\) .
-
Show that \(C_6\) and the graph consisting of two disjoint triangles have the same degree list and are not isomorphic. Then state how many graphs on six vertices with every degree equal to \(3\) there are up to isomorphism, referring to Example 6.2.
Answer
Both graphs have degree list \(2,2,2,2,2,2\) . \(C_6\) is connected and the two triangles are not; alternatively, one contains a triangle and the other does not. Up to isomorphism there are exactly two graphs on six vertices with all degrees \(3\) : the graphs \(G_1\) and \(G_3\) of Example 6.2.
-
Draw all trees with five vertices and all trees with six vertices up to isomorphism, give the degree list of each, and say how you know that no two of your drawings are isomorphic.
Answer
Five vertices, three trees: the path, with degrees \(2,2,2,1,1\) ; the star, \(4,1,1,1,1\) ; and the tree with degrees \(3,2,1,1,1\) . Six vertices, six trees: the path, \(2,2,2,2,1,1\) ; the star, \(5,1,1,1,1,1\) ; a tree with degrees \(4,2,1,1,1,1\) ; a tree with degrees \(3,3,1,1,1,1\) ; and two trees with degrees \(3,2,2,1,1,1\) , in one of which the vertex of degree \(3\) is adjacent to two leaves and in the other to one leaf. Different degree lists show non-isomorphism, and the last two are separated by the number of leaves adjacent to the vertex of degree \(3\) .
-
Prove that if a graph \(G\) is not connected, then its complement, as defined in Exercise 4, is connected. Treat separately two vertices in different components of \(G\) and two vertices in the same component.
Solution
Write \(\overline G\) for the complement, and let \(u\) and \(v\) be two vertices. We find a walk from \(u\) to \(v\) in \(\overline G\) .
Case 1: \(u\) and \(v\) lie in different components of \(G\) . Then \(uv\) is not an edge of \(G\) , because adjacent vertices lie in the same component. So \(uv\) is an edge of \(\overline G\) .
Case 2: \(u\) and \(v\) lie in the same component of \(G\) . Since \(G\) is not connected, there is a vertex \(w\) in a different component. By Case 1, both \(uw\) and \(wv\) are edges of \(\overline G\) , so \(u,w,v\) is a walk in \(\overline G\) .
In both cases \(u\) and \(v\) are joined by a walk of length at most \(2\) in \(\overline G\) . Hence \(\overline G\) is connected. The hypothesis that \(G\) is disconnected was used in Case 2, to supply the vertex \(w\) .
-
Let \(T\) be a tree with a vertex of degree \(d\ge 1\) . Prove that \(T\) has at least \(d\) leaves, by removing that vertex and applying Lemma 6.10 to each resulting component with care for components consisting of one vertex.
Solution
Let \(v\) be a vertex of degree \(d\) with neighbours \(w_1,\dots,w_d\) , and remove \(v\) with its edges. The remaining graph has no cycle. Each of its components contains at least one \(w_i\) , because in \(T\) every vertex is joined to \(v\) by a path, and the vertex just before \(v\) on that path is a neighbour of \(v\) . No component contains two of the \(w_i\) : a path between \(w_i\) and \(w_j\) avoiding \(v\) , together with the edges \(vw_i\) and \(vw_j\) , would be a cycle in \(T\) . So there are exactly \(d\) components, each a tree containing exactly one neighbour of \(v\) .
Consider one component. If it is a single vertex, that vertex is some \(w_i\) , and its only neighbour in \(T\) is \(v\) , so it is a leaf of \(T\) . If it has at least two vertices, Lemma 6.10 gives it two leaves; at most one of them is the neighbour of \(v\) , so at least one is not adjacent to \(v\) and has the same degree, \(1\) , in \(T\) . Either way the component contains a leaf of \(T\) . Different components give different leaves, so \(T\) has at least \(d\) leaves.
-
A tree has \(k\) vertices of degree \(3\) , and all its other vertices are leaves. Use Theorems 6.2 and 6.12 to find the number of leaves in terms of \(k\) . Then find the number of leaves of a tree with \(n\) vertices of degree \(4\) and all other vertices leaves.
Solution
Let \(\ell\) be the number of leaves. The tree has \(\ell+k\) vertices, hence \(\ell+k-1\) edges by Theorem 6.12. The sum of the degrees is \(\ell\cdot 1+k\cdot 3\) , and by the handshake lemma it equals twice the number of edges:
\[ \ell+3k=2(\ell+k-1). \]Solving, \(\ell=k+2\) .
In the second situation, with \(n\) vertices of degree \(4\) and \(\ell\) leaves, the same two theorems give \(\ell+4n=2(\ell+n-1)\) , so \(\ell=2n+2\) . This is the count of hydrogen atoms in a saturated hydrocarbon with \(n\) carbon atoms, whose molecule is a tree with carbons of degree \(4\) and hydrogens of degree \(1\) . For example \(k=1\) gives the star with three leaves, and \(n=1\) gives the star with four.
-
Prove that a graph is a tree if and only if it is connected and the removal of any one edge leaves a disconnected graph.
Solution
Let \(G\) have \(n\) vertices.
Suppose first that \(G\) is a tree. Then \(G\) is connected, and by Theorem 6.12 it has \(n-1\) edges. Removing any edge leaves a graph with \(n\) vertices and \(n-2\) edges, which by Theorem 6.8 has at least \(2\) components. So the removal of any edge disconnects \(G\) .
Conversely, suppose \(G\) is connected and the removal of any edge disconnects it. If \(G\) contained a cycle, then by Lemma 6.13 removing an edge of that cycle would leave a connected graph, contrary to the hypothesis. So \(G\) has no cycle, and being connected it is a tree.
Trees are thus the minimally connected graphs: connected, with no edge to spare.
-
Let \(T\) be a tree and let \(u\) , \(v\) be two vertices of \(T\) that are not adjacent. Prove that adding the edge \(uv\) to \(T\) creates a graph with exactly one cycle.
Hint
By Theorem 6.14(d) there is exactly one path in \(T\) from \(u\) to \(v\) ; with the new edge it forms a cycle. For uniqueness, note that a cycle in the new graph must use the edge \(uv\) , since \(T\) has no cycle, and the rest of that cycle is a path in \(T\) from \(u\) to \(v\) .
-
How many spanning trees does the cycle \(C_n\) have? How many does the graph obtained from \(K_4\) by deleting one edge have? Justify both answers by describing which sets of edges are spanning trees.
Answer
\(C_n\) has \(n\) spanning trees: a spanning tree has \(n-1\) of the \(n\) edges, and removing any one edge leaves a path. \(K_4\) minus an edge has \(5\) edges, and a spanning tree is a set of \(3\) of them containing no cycle; of the \(\binom 53=10\) sets of three edges, exactly \(2\) are triangles, so there are \(8\) spanning trees.
-
Claim: every tree with \(n\) vertices has \(n-1\) edges. Proposed proof: “Base case: one vertex, no edges. Step: take a tree with \(k\) vertices and \(k-1\) edges, add a new vertex, and join it to one old vertex; the result is a tree with \(k+1\) vertices and \(k\) edges.” The claim is true. Explain why the argument does not prove it, and say which lemma of this chapter repairs it.
Solution
The step shows that if a tree with \(k\) vertices has \(k-1\) edges, then any graph made from it by attaching one new vertex with one edge has \(k\) edges. That is true. But the inductive step for the claim must cover every tree with \(k+1\) vertices, and the argument says nothing about a tree with \(k+1\) vertices unless that tree is known to arise by attaching a vertex of degree \(1\) to a tree with \(k\) vertices. This is the build-up error of Example 6.5: the argument starts from the smaller object and enlarges it, and never shows that all larger objects are reached.
The missing fact is true and is supplied by Lemmas 6.10 and 6.11: every tree with at least two vertices has a leaf, and removing it leaves a tree. With these, the proof is run in the correct direction, as in Theorem 6.12: take an arbitrary tree with \(k+1\) vertices, remove a leaf, apply the hypothesis, and restore the leaf.
-
Decide whether each graph is bipartite, giving a two-colouring or an odd cycle: (a) \(C_8\) ; (b) the cube graph \(Q_3\) on bit strings of length \(3\) ; (c) \(K_4\) with one edge deleted; (d) the graph on \(\{1,\dots,8\}\) in which \(i\) and \(j\) are adjacent when \(\lvert i-j\rvert\) is \(1\) or \(4\) .
Solution
(a) Bipartite. Colour the vertices \(v_1,\dots,v_8\) alternately; since \(8\) is even, \(v_8\) and \(v_1\) receive different colours.
(b) Bipartite. Let \(X\) be the strings with an even number of ones and \(Y\) those with an odd number. Adjacent strings differ in exactly one position, so the number of ones changes by one and every edge joins \(X\) to \(Y\) .
(c) Not bipartite. Delete the edge \(34\) from \(K_4\) on \(\{1,2,3,4\}\) ; the edges \(12\) , \(23\) , \(13\) remain and form a triangle, an odd cycle.
(d) Not bipartite. The walk \(1,2,3,4,5,1\) is a cycle of length \(5\) : consecutive labels differ by \(1\) , and \(5\) and \(1\) differ by \(4\) . By Theorem 6.18 no two-colouring exists.
-
Prove that the cube graph \(Q_n\) on bit strings of length \(n\) is bipartite, that every vertex has degree \(n\) , and that it has \(n2^{n-1}\) edges.
Hint
For bipartiteness, use the parity of the number of ones, as in Exercise 6.14(b). Each string has exactly \(n\) neighbours, one for each position that can be changed. Then apply the handshake lemma to \(2^{n}\) vertices of degree \(n\) .
-
Find the chromatic number of \(C_n\) for each \(n\ge 3\) , of \(K_n\) , and of the wheel obtained from \(C_5\) by adding one new vertex adjacent to all five. In each case give a colouring and a reason why fewer colours are impossible.
Answer
\(\chi(C_n)=2\) for even \(n\) , by alternating colours, and \(3\) for odd \(n\) , where two colours are impossible by Theorem 6.18 and three suffice by alternating two colours and giving the last vertex a third. \(\chi(K_n)=n\) , since all vertices are mutually adjacent. The wheel has chromatic number \(4\) : the rim \(C_5\) needs three colours, and the hub, adjacent to all rim vertices, needs a fourth.
-
Six committees have members as follows: \(A=\{1,2\}\) , \(B=\{2,3\}\) , \(C=\{3,4\}\) , \(D=\{4,5\}\) , \(E=\{5,1\}\) , \(F=\{1,3\}\) . Two committees cannot meet at the same time if they share a member. Draw the conflict graph and find the least number of meeting times, with evidence on both sides.
Solution
Two committees conflict when they share a member. The conflicts are \(AB\) (member \(2\) ), \(BC\) (member \(3\) ), \(CD\) (member \(4\) ), \(DE\) (member \(5\) ), \(EA\) (member \(1\) ), \(AF\) and \(EF\) (member \(1\) ), and \(BF\) and \(CF\) (member \(3\) ): nine edges. The committees \(A,B,C,D,E\) form a cycle of length \(5\) , and \(F\) is adjacent to \(A\) , \(B\) , \(C\) , and \(E\) .
Three meeting times suffice. Let \(A\) and \(C\) meet first, \(B\) and \(E\) second, \(D\) and \(F\) third. None of the pairs \(AC\) , \(BE\) , \(DF\) is an edge, so no two committees meeting together share a member.
Two are not enough. The committees \(A\) , \(B\) , \(F\) are pairwise in conflict, through members \(2\) , \(1\) , and \(3\) , so they form a triangle and need three different times.
The least number of meeting times is \(3\) . The colouring is the evidence that three are enough and the triangle is the evidence that two are not.
-
For which \(n\) does \(K_n\) have an Euler circuit? For which \(m\) and \(n\) does \(K_{m,n}\) have one? For which \(n\) does the cube graph \(Q_n\) have one?
Answer
\(K_n\) : exactly when \(n\) is odd, since every degree is \(n-1\) . \(K_{m,n}\) : exactly when \(m\) and \(n\) are both even, since the degrees are \(m\) and \(n\) . \(Q_n\) : exactly when \(n\) is even, since every degree is \(n\) . All these graphs are connected.
-
Let \(u\) and \(v\) be different vertices of a connected graph. Prove that there is a trail from \(u\) to \(v\) using every edge exactly once if and only if \(u\) and \(v\) are the only vertices of odd degree, by adding a new vertex adjacent to \(u\) and \(v\) and applying Theorem 6.22.
Hint
Add a new vertex \(z\) adjacent to \(u\) and \(v\) only. The new graph is connected, and its degrees are all even exactly when \(u\) and \(v\) were the only odd vertices. An Euler circuit of the new graph, started at \(z\) , begins \(z,u,\dots\) and ends \(\dots,v,z\) ; delete \(z\) . Conversely a trail from \(u\) to \(v\) using every edge closes up through \(z\) into an Euler circuit.
-
Show that “is isomorphic to” is reflexive, symmetric, and transitive, so that it is an equivalence relation on any set of graphs. Identify the facts about bijections from Chapter 2 that each of the three properties uses.
Hint
Reflexive: the identity function is an isomorphism. Symmetric: the inverse of an isomorphism is a bijection by Theorem 2.9 and preserves edges and non-edges because the condition in Definition 6.4 is an “if and only if”. Transitive: a composition of bijections is a bijection by Theorem 2.8, and the edge condition passes through both.
-
How many graphs are there with vertex set \(\{1,2,3,4\}\) ? How many of them have exactly three edges, and how many are connected? Organize the count of connected graphs by the number of edges.
Answer
There are \(2^{6}=64\) graphs and \(\binom 63=20\) with three edges. Connected graphs by number of edges: \(16\) with three edges (the trees), all \(15\) with four edges, all \(6\) with five, and \(1\) with six, a total of \(38\) . A graph with four or more edges on four vertices cannot be disconnected, since a disconnected graph on four vertices has at most \(3\) edges.
-
Prove that a connected graph with \(n\) vertices and exactly \(n\) edges contains exactly one cycle.
Hint
Take a spanning tree, which has \(n-1\) of the \(n\) edges. The one remaining edge joins two vertices of the tree; apply Exercise 11 to see that there is at least one cycle, and for uniqueness show that every cycle of the graph must contain that edge.
-
Let \(G\) be a graph in which every vertex has degree at least \(\delta\) , where \(\delta\ge 2\) . By considering a longest path, prove that \(G\) contains a cycle of length at least \(\delta+1\) .
Solution
Let \(v_0,v_1,\dots,v_k\) be a path of greatest length in \(G\) . Every neighbour of \(v_0\) lies on this path, since a neighbour \(w\) off the path would give the longer path \(w,v_0,\dots,v_k\) . The vertex \(v_0\) has at least \(\delta\) neighbours, and they are among \(v_1,\dots,v_k\) . Let \(v_j\) be the neighbour of \(v_0\) with the largest index. Since at least \(\delta\) different indices from \(1\) to \(j\) are indices of neighbours, \(j\ge\delta\) .
Now \(v_0,v_1,\dots,v_j,v_0\) is a closed walk whose vertices \(v_0,\dots,v_j\) are all different, and its length is \(j+1\ge\delta+1\ge 3\) . So it is a cycle of length at least \(\delta+1\) . The argument is the same extremal idea as in Lemma 6.10: the end of a longest path has all its neighbours on the path.