Math 485, Graph Theory: Homework #2

Stephen G. Simpson

Due Wednesday, October 5, 2009

The assignment consists of Exercises 1.2.8, 1.2.20, 1.2.21, 1.2.30, 1.3.21, 1.3.24, 1.3.26, 1.4.11, 1.4.14, 1.4.18, 1.4.22, 1.4.27 of the textbook by West. Each exercise counts for 10 points. Here are some (rather sketchy) solutions.

1.2.8. We know that a graph G is Eulerian if and only if G is connected and all vertices are of even degree. Obviously K_{mn} is connected. The degrees of the vertices in K_{mn} are m and n, so K_{mn} is Eulerian if and only if m and n are both even. In this case, an interesting exercise is to explicitly construct a closed Eulerian trail in K_{mn}.

1.2.20. Let G be a simple graph. Let v be a cut-vertex in G. Let H_{1}, …, H_{k} be the components of G − v. Note that k ≥ 2. Clearly \overline{G} − v contains all edges with one end in H_{i} and the other in H_{j} where i ≠ j. Hence, each pair of vertices in H_{1} ∪ ⋯ ∪ H_{k} is connected by a path of length 1 or 2 in \overline{G} − v. In particular \overline{G} − v is connected.

1.2.21. Let G be a simple graph. Easy observation: if G is not connected then \overline{G} is connected. (Proof: Let G_{1} be one of the components of G, and let G_{2} be the union of the remaining components. Then \overline{G} contains all edges with one end in G_{1} and the other in G_{2}. Hence, each pair of vertices in G is connected by a path of length 1 or 2 in \overline{G}. In particular \overline{G} is connected.)

Now assume that G is self-complementary, i.e., G ≅ \overline{G}. It follows from the above observation that G is connected. Also, since K_{2} is not selfcomplementary, G must have ≥ 3 vertices.

Claim 1: If G contains a vertex of degree 1, then G contains a cut-vertex.

Proof: Let u be a vertex of degeee 1. Let v be the unique vertex to which u is adjacent. Let w be a vertex other than u and v. Since G is connected, there is a path from u to w. However, any path from u to w goes through v. In other words, G − v contains no path from u to w. Thus v is a cut-vertex, Q.E.D.

Claim 2: If G contains a cut-vertex, then G contains a vertex of degree 1.

Proof: Let v be a cut-vertex in G. Then G − v has ≥ 2 components. If any of these components consists of only one vertex, then that vertex is of degree 1 and we are done. Thus we may assume that each of these components has at least two vertices. If v is of degree 1 in \overline{G} then we are done since G ≅ \overline{G}. Thus we may assume that v is of degree ≥ 2 in \overline{G}. Under these assumptions, we now assert that \overline{G} has no cut-vertex. This will contradict the fact that G ≅ \overline{G} and thereby complete the proof of Claim 2. To prove our assertion, note first that v itself is not a cut-vertex in \overline{G} in view of Exercise 20. Now let w be a vertex other than v. Let H_{1} be the component of G − v to which w belongs, and let H_{2} be the union of the remaining components of G − v. We know that H_{1} has at least two vertices, and each vertex of H_{1} − w is adjacent in \overline{G} − w to each vertex of H_{2}. Moreover, since v is of degree ≥ 2 in \overline{G}, v is adjacent in \overline{G} − w to some other vertex in \overline{G} − w. Thus we see that \overline{G} − w is connected, hence w is not a cut-vertex of \overline{G}. This proves our assertion, Q.E.D.

1.2.30. Let A be the adjacency matrix of G. Let a_{ij}^{(k)} be the ij-entry of A^{k}. We claim that a_{ij}^{(k)} is equal to the number of ij-walks of length k. We prove this by induction on k. For the base step k = 1 it is obvious, since a walk of length 1 is just an edge. For the induction step, recall that a_{ij}^{(k+l)} is the sum of the products a_{is}^{(k)}a_{sj}^{(l)} for all s. By induction hypothesis, this product is equal to the number of is-walks of length k times the number of sj-walks of length l. Thus the sum a_{ij}^{(k+l)} is equal to the total number of ij-walks of length k + l. This completes the proof of our claim.

Let n be the number of vertices in G, and let r be the odd number which is equal to either n or n − 1. If G contains an odd cycle, then G contains an odd closed walk of length r. (This can be seen by repeating an edge in opposite directions.) Conversely, if G contains an odd closed walk of any length, then G contains an odd cycle. (This is Lemma 1.2.15 in the textbook.) It now follows by Theorem 1.2.18 that G is bipartite if and only if G contains no closed walk of length r. In other words, G is bipartite if and only if a_{ii}^{(r)} = 0 for all i.

1.3.21. We wish to count the number of 6-cycles in K_{m,n}. Let X, Y be the partite sets of size m, n respectively. The number of directed 6-cycles v_{1}v_{2}v_{3}v_{4}v_{5}v_{6} starting with v_{1} ∈ X is mn(m − 1)(n − 1)(m − 2)(n − 2) because there are m choices for v_{1}, then n choices for v_{2}, then m − 1 choices for v_{3}, etc. To get the number of undirected 6-cycles regardless of starting point, we must divide by 6, because the same cycle can be obtained starting at any of v_{1}, v_{3}, v_{5} or in reverse. Thus the number of 6-cycles in K_{m,n} is mn(m − 1)(n − 1)(m − 2)(n − 2)/6.

1.3.24. Suppose x, y, u, v, w is a copy of K_{2,3} in Q_{n} with partite sets x, y and u, v, w. Think of these vertices as binary words of length n, say x = x_{1} ⋯ x_{n} and similarly for y, u, v, w. The three binary words u, v, w are obtained from the binary word x by flipping three different bits. Thus x can be recovered from u, v, w by “majority vote”: each bit x_{i} agrees with at least two of the three bits u_{i}, v_{i}, w_{i}. Similarly y can be recovered from u, v, w in exactly the same way. Thus x = y, a contradiction. We conclude that Q_{n} contains no copy of K_{2,3}.

1.3.26. To count the 6-cycles in Q_{3}, note that each 6-cycle in Q_{3} either (i) meets every face of Q_{3} in two adjacent edges, or (ii) meets two adjacent faces of Q_{3} in three edges each. In case (i) our 6-cycle is determined once we know which two adjacent edges of the top face belong to it. This pair of edges is determined by its common vertex, which can be any vertex in the top face. Since the top face has four vertices, there are four 6-cycles of type (i). In case (ii) our 6-cycle is determined by the two adjacent faces. Moreover, these two faces are determined by their common edge, which can be any edge of Q_{3}. Since Q_{3} has 12 edges, there are 12 6-cycles of type (ii). Altogether the number of 6-cycles in Q_{3} is 4 + 12 = 16.

Each 6-cycle in Q_{n} involves flipping exactly three bits and so is contained in exactly one copy of Q_{3} within Q_{n}. Each copy of Q_{3} is determined by choosing a set of three bits to be flipped, plus values for the remaining n − 3 bits. Thus the number of copies of Q_{3} is 2^{n−3} · (n choose 3). Finally, the number of 6-cycles in Q_{n} is 16 · 2^{n−3} · (n choose 3), or in other words 2^{n}n(n − 1)(n − 2)/3.

1.4.11. Let G be a digraph. Let G_{1}, …, G_{k} be the strong components of G. Form a digraph H with vertices v_{1}, …, v_{k} by letting v_{i}v_{j} be an edge in H if and only if i ≠ j and G contains an edge from G_{i} to G_{j}. Obviously H is acyclic, because otherwise all the G_{i}’s corresponding to v_{i}’s in a cycle of H would be included in one strong component of G. Since H is acyclic, it contains at least one vertex of out-degree 0. If v_{i} is such a vertex, G_{i} has no exiting edges. We have now shown that some strong component of G has no exiting edges. Applying the same argument with edges reversed, we show that some strong component of G has no entering edges. (These two strong components do not have to be the same.)

1.4.14. Let G be a digraph with no cycles. In G choose a vertex of in-degree 0 and call it v_{1}. In G − v_{1} choose a vertex of in-degree 0 and call it v_{2}. In G − v_{1}, v_{2} choose a vertex of in-degree 0 and …, etc. Thus we obtain an ordering of the vertices v_{1}, v_{2}, … such that i < j for all edges v_{i}v_{j}.

1.4.18. Let G be a digraph with no cycles. Given a vertex u of G, consider the 2-player positional game starting at u. In this game Player I chooses v succeeding u, then Player II chooses w succeeding v, etc. The loser is the first player who cannot choose a vertex. Let S be the set of vertices u such that there is no winning strategy for Player I starting at u. For each u ∉ S let σ_{u} be a winning strategy for Player I starting at u.

Claim 1: Given u ∈ S, for all v succeeding u there exists w succeeding v such that w ∈ S. Otherwise, let v be a successor of u such that for all w succeeding v, w ∉ S. Consider the following strategy for Player I starting at u: first choose v, then wait for Player II to choose w succeeding v, then play according to σ_{w}. Clearly σ is a winning strategy for Player I starting at u. Hence u ∉ S. This contradiction proves our claim.

Claim 2: For each u ∈ S there is a winning strategy for Player II starting at u. Namely, consider a strategy τ whereby Player II always chooses a vertex in S if possible. By Claim 1 this is always possible, provided the game starts at u. Since G has no cycles, any play of the game must eventually end in a vertex of out-degree 0. At this point Player II has won. Thus τ is a winning strategy for Player II starting at u.

Claim 3: S is a kernel of G. First, assume u ∈ S and let v be any successor of u. If v ∈ S, then by Claim 2 there is a winning strategy τ for Player II starting at v. Let σ be the following strategy for Player I starting at u: first choose v, then play according to τ. Clearly σ is a winning strategy for Player I starting at u. Hence u ∉ S, a contradiction. Second, assume u ∉ S and let v be Player I’s first move according to σ_{u}. Then v is a successor of u and there is no winning stragegy for Player I starting at v. Hence v ∈ S. This completes the proof that S is a kernel.

Claim 4: S is the only kernel of G. If S and T are two different kernels, then clearly each vertex in S \ T has a successor in T \ S and vice versa. After a finite number of steps this eventually leads to a cycle, a contradiction. This proves Claim 4. (Note also that the cycle is even!)

1.4.22. Let G be a digraph with d^{+}(v) = d^{−}(v) for all vertices except x and y. By the degree sum formula for digraphs we have d^{+}(x) − d^{−}(x) = d^{−}(y) − d^{+}(y) ≠ 0. Interchanging x and y if necessary, we may assume d^{+}(x) − d^{−}(x) = k > 0. Let G′ consist of G with the addition of k edges from y to x, call them e_{1}, …, e_{k}. Then G′ has d^{+}(v) = d^{−}(v) for all vertices. Let H be the component of G′ containing x and y. By Euler’s Theorem for digraphs, H is Eulerian. Let C be an Eulerian circuit in H. Then C − e_{1}, …, e_{k} consists of k pairwise edge-disjoint xy-paths in G.

1.4.27. Let A be an alphabet of size k. Let n be a positive integer. Consider the digraph G whose vertices are all words of length n − 1 on the alphabet A and whose edges are of the form

a_{1} ⋯ a_{n−1} ⟶^{a_{n}} a_{2} ⋯ a_{n}

where the edge is labeled with a_{n}. Thus G has k^{n−1} vertices and k^{n} edges, and each vertex has d^{+} = d^{−} = k. Moreover G is strongly connected, because we can walk from any vertex a_{1} ⋯ a_{n−1} to any other vertex b_{1} ⋯ b_{n−1} by successively following n − 1 edges labeled b_{1}, …, b_{n−1}. Thus G is Eulerian. Letting C be an Eulerian circuit in G, we see that the labels on the edges of C form a cyclic word of length k^{n} and each word of length n occurs exactly once in this cyclic word. Thus we have a DeBruijn sequence for the words of length n on the alphabet A.