Diestel soln\' - Graph Theory. PDF

Preview

Summary

Graph Theory....

Description

Selected Solutions to Graph Theory, 3rd Edition

Reinhard Diestel

Rakesh Jana Department of Mathematics

IIT Guwahati March 1, 2016

Acknowledgement These solutions are the result of taking CS-520(Advanced Graph Theory) course in the Jan-July semester of 2016 at Indian Institute of Technology Guwahati. This is not a complete set of solutions in that book. It may happen that solution of some problem may be wrong. I have not verified these problem from some expart. It is my kind request you that do not belive the answer blindly. If you found any mistake please inform me. I know these article must contain some typographical errors, in that case please inform me. If you have any better solution in any of these problem please let me know. I will upload that solution in this content with your name. If you want to discuss any of these solution with me please ping me in my given email address or meet me in research scholar office (RS-E1-010) Department of Mathematics, IIT Guwahati. You can find List of Solved Exercises at the end. Please e-mail jana.rakesh. [email protected] or [email protected] for any corrections and suggestions.

c Copyright 2015–2016, Rakesh Jana

Contents 1 The Basics

3

2 Matching, Covering and Packing

10

3 Connectivity

14

4 Planar Graphs

18

5 Colouring

19

6 Some Arbitary Problem 1 The Basics . . . . . . 2 Matching . . . . . . . 3 Connectivity . . . . . 4 Planar graph . . . . . 5 Colouring . . . . . . .

. . . . .

7 Solved Exercise Reference

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

21 21 21 23 23 23 26

Rakesh Jana

1

IIT Guwahati

The Basics

See some extra problem on basic in the end( problem-6.1.1 - problem-6.1.2). Exercise 1.1. What is the number of edges in K n ? Proof. Notice that first vertex adjacent to other n − 1 vertices. Now compute how many vertices are adjacent to second vertex except first vertex, obviously answer is n − 2. Similarly compute how many vertices are adjacent to third vertex except first and second vertices, answer is n − 3, and so on. Thus total number of edge is K n is (n − 1) + (n − 2) + · · · + 1 + 0 =

n(n − 1) . 2

Exercise 1.2. Determine the average degree, number of edges, diameter, girth, and circumference of the hypercube graph Qd . Proof. Since V is the set of all 0 − 1 sequences of length d. Thus total number of vertices is 2d , since in each place we can assign two number 0, 1. Since two such sequence form an edge if and only if they differ in exactly one position. Thus each vertices has degree d. Now we know that X d(v) 2|E| = v∈V

|E| = • Thus average degree of Qd =

d × 2d = d × 2d−1 . 2

2|E| |V |

= d.

• Notice that the distance between any two vertices depends on the number of different bits, so diameter is d, i.e. diam G = d. • Girth(Q1 ) = ∞, because there are no cycles on hypercube graph Q1 . ∼ K 2 × Qd−1 . Girth(Qd ) = 4, where d ≥ 2, this is because Qd = • Circumference of Qd is 2d . Exercise 1.3. Let G be a graph containing a cycle C, and assume that G contains a path of length at √ least k between two vertices of C. Show that G contains a cycle of length at least k. Is this best possible? 3

Rakesh Jana

IIT Guwahati

Proof. Let the path P start at x and end at y where x, y are lie on C. Suppose that P leaves C for the ith time at vertex xi , and arrives at C for the ith time at vertex yi (it is possible for xi+1 = yi ). Then the xi , yi -portion of P together with the xi , yi -portion of C forms a cycle of length at least 1 + li , where li = distP (xi , yi ). Let among xi ’s and √ yi ’s there are t many distict vertices. Without loss of any generality Now if t ≥ k then we can take a path along C connecting √ these distinct vertices and√then traverse C then we will get a cycle of length atleast k + 1. Let t < k. Let us consider subpath of path P , Pi = xi P yi and P¯i = yi P xi+1 . Then there are atmost t many internally disjoint subpath of P . Let Pk be the subpath of P with maximum length, say l(pk ) = m. Then k ≤ l(P ) ≤ tm √ ≤ km

√ √ Thus m > k. Hence we have a subpath of the path P of lenght atleast k whose √ end points are in C and also distinct. Hence We get a cycle of length atleast k. √ √ Notice in the solution that we can improve the size of cycle from k to k + 1. Exercise 1.4. We know that from proposition 1.3.2 that every graph containing a cycle satisfying g(G) ≤ 2 diam G + 1. Is the bound is best possible? Proof. Yes. It is the best possible bound because equality occur when G = K 3 . Exercise 1.5. Show that rad G ≤ diam G ≤ 2 rad G. Proof. We know that diam G = maxx,y∈v(G) dG (x, y). max dG (x, y)

rad G = min

x∈V (G) y∈V (G)

≤ min

max diam G

x∈V (G) y∈V (G)

= diam G. To show diam G ≤ 2 rad G. Let a, b, v ∈ V (G) such that dG (a, b) = diam G and rad G = maxy∈V (G) dG (v, y). diam G = dG (a, b) ≤ dG (a, v) + dG (v, b) ≤ rad G + rad G = 2 rad G.

4

Rakesh Jana

IIT Guwahati

Exercise 1.6. Prove the weakening of Theorem 1.3.4 obtained by replacing average with minimum degree. Deduce that |G| ≥ n0 (d/2, g) for every graph G as given in the theorem. Proof. Case 1: Consider g = 2r + 1, r ∈ N. This proof is similar to proof of proposition 1.3.3. Let v ∈ V (G) be any vertex in G. Let us consider Di = {u ∈ V (G) : dG (u, v) = i}, for i ∈ N∪{0}. It is clear that Di ∩Dj = ∅, ∀i 6= j and V (G) = ∪i≥0 Di . Since v can not contained in any cycle of length lesser then 2r + 1. Thus for any u, w ∈ Di , 0 ≤ i ≤ r − 1, N (u) ∩ Di+1 is disjoint from N (w) ∩ Di+1, otherwise we can construct a cycle of length atmost r − 1 + 1 + 1 + r − 1 = 2r < 2r + 1, a contradiction. Hence each vertex in Di , 0 ≤ i ≤ r − 1 is connected to exactly one vertex in Di−1 and atleast δ − 1 vertices in Di+1. Hence |D0 | = 1, |D1 | ≥ δ and |Di | ≥ δ(δ − 1)i−1 , for 2 ≤ i ≤ r. Thus |V (G)| ≥

r−1 [ i=0

|Di | = 1 + δ

r−1 X i=0

(δ − 1)i−1 .

Case-2: Consider g = 2r, r ∈ N. In this case proof is same as previous one instead of a vertex we have to start with two adjacent vertices. Let uv ∈ E(G). Similar way consider for i ∈ N ∪ {0}, ˆ y) = i} Diu = {y : d(u, ˆ y) = i} Dv = {y : d(v, i

where dˆ(x, y) := dG−uv (x, y). Similar way as case-1, for any x ∈ {u, v}, Dix ∩ Djx = ∅ x x is disjoint from N (b) ∩ Di+1 for i 6= j and for any a, b ∈ Dix, N (a) ∩ Di+1 for x 1 ≤ i < r − 1. Also each vertex in D i (0 ≤ i < r − 1) is connected to exactly one x . Now |D0x| = 1, |D1x| ≥ δ − 1 and vertex in Dxi−1 and atleast δ − 1 vertices in Di+1 x i |D i | ≥ (δ − 1) , for 1 ≤ i ≤ r − 1. Let us define for x ∈ {u, v}, [ Dxi . Tx = 0≤i≤r−1

Pr−1 (δ − 1)i for any x ∈ {u, v}. Notice that |Tx | = i=0 Claim. Tu ∩ Tv = ∅. To prove this claim first notice that Diu ∩ Dvj = ∅, for all 0 ≤ i, j ≤ r − 1. If not let x ∈ Diu ∩ Djv for some 0 ≤ i, j ≤ r − 1. Then there exist a cycle in G of length atmost r − 1 + r − 1 + 1 = 2r − 1 < 2r, a contradiction. Hence Tu ∩ Tv = ∅. Pr−1 Hence |V (G)| ≥ |Tu | + |Tv | = 2 i=0 (δ − 1)i . 5

Rakesh Jana

IIT Guwahati

Lemma 1.1. Let P be a path in a connected graph G. If there is u ∈ V (G) \ V (P ), then there exist v ∈ V (G) \ V (P ) adjacent to P . Proof. Let u ∈ V (G) \ V (P ) and w ∈ V (P ). Since G is connected there exist a u − w path in G, say Q. Now consider last common vertex p ∈ V (P ) ∩ V (Q) (traversing from w to u) then there exist a vertex in v ∈ V (Q) \ V (P ) such that vp ∈ E(G). Exercise 1.7. Show that every connected graph G contains a path of length at least min{2δG, |G| − 1}. Proof. Let us consider P = x0 x1 · · · xk be a longest path in G. We have to show k ≥ min{2δG, |G| − 1}. If possible let k < min{2δG, |G| − 1}. Now G is connected |E(G)| ≥ |G| − 1. Since k < |G| − 1 there exist u ∈ V (G) \ V (P ) and by lemma 1.1 there exist y ∈ V (G) \ V (P ) such that yxi ∈ E(G), for some 0 ≤ i ≤ k. Now if x0 xk ∈ E(G) we can get a path P ′ = yxi P xk x0 P x ˚i which is longer then P , a contradiction. Thus x0 xk ∈ / E(G). Now N (x0 ) ⊆ V (P ) and N (xk ) ⊆ V (P ), since P is the longest path. Let us consider S = {xj |xj+1 ∈ N (x0 ), 0 ≤ j ≤ k − 2}. Clearly |S| ≥ δ (G). Since k < 2δ (G) gives |V (P ) \ (S ∪ {xk })| ≤ δ(G). By pigeonhole principle there exist xj ∈ S such that xj xk ∈ E(G). Hence we get a cycle C = x0 P xj xk P xj+1x0 . Now consider the path P ∗ = yxi C x ˚i which is longer then P , a contradiction. Hence k ≥ min{2δG, |G| − 1}. Exercise 1.8. Find a good lower bound for the order of a connected graph in terms of its diameter and minimum degree. Proof. The following claim gives the lower bound for the order of connected graph. Claim. Let G be any connected graph with diam G = k and δ(G) = d then |G| ≥ kd/3. Let dG (x, y) = k, for some x, y ∈ V (G) and distance achieve by the path P = x0 x1 · · · xk , where x0 = x, xk = y. Let u be a vertex not on P that is adjacent to some vertex on P . Let i be the smallest integer such that xi is adjacent to v. Notice that if v is adjacent to xj for j > i + 2 then we can get a path x0 P xi vxj P xk and which is shorter then P , a contradiction to dG (x, y) = k. Hence each v ∈ V (G) \ V (P ) can adjacent to at most 3 vertices on P . Exercise 1.10. Show that every 2-connected graph conatains a cycle.

6

Rakesh Jana

IIT Guwahati

Proof. Let G be a 2-connected graph. Then δ(G) ≥ 2, since if d(v) = 1 or 0, for some v ∈ V (G) then that vertex will be either a cut vertex or isolated, in both case it contradict that G is 2-connected. Hence by proposition-1.3.1, it has a cycle of length atleast δ(G) + 1. Exercise 1.11. Determine κ(G) and λ(G) for G = P m , C n , K n , Km,n , and Qd ; d, m, n ≥ 3. Proof. Recall. κ(G) denote for connectivity(vertex) of a graph G and λ(G) denote edge-connectivity of graph G. Also by proposition-1.4.2, κ(G) ≤ λ(G) ≤ δ (G). Given graphs are all connected. κ(P m ) = 1, for m ≤ 2 it is clear, for m > 2 if you remove an interior vertex of Pm , it becomes a disconnect graph. λ(Pm ) = 1, as if you delete any edge, the graph becomes disconnected. κ(C n ) = 2, because if you remove any vertex you will get P n−1 , hence if you delete any two vertex from Cn then it becomes a disconnect graph. λ(C n ) = 2, as if you delete any edge, the graph becomes P n and if you delete one more edge it become disconnected. Similarly, κ(K n ) = n − 1 λ(K n ) = n − 1 κ(Km,n ) = min{m, n} λ(Km,n ) = min{m, n} κ(Qd ) = d λ(Qd ) = d. Exercise 1.12. Is there any function f : N → N such that, for all k ∈ N, every graph of minimum degree atleast f (k) is k connected? Proof. No. Suppose f (1) = t ∈ N. Then there exist graphs G and H with both have minimum degree t but one of them is connected and other is not. For instance take G = K t+1 and take H be two disjoint component of K t+1. Exercise 1.16. Show that every tree T has atleast ∆(T ) leaves. Proof. Exercise 1.17. Show that a tree without a vertex of degree 2 has more leaves than other vertices. Can you find a very short proof that does not use induction?

7

Rakesh Jana

IIT Guwahati

Proof. Let T be a tree with no vertex of degree 2. Let Vi = {v ∈ V (G) : dG (v) = i}. < 2. Now Notice that V2 = ∅. Now average degree of a tree is 2|E| = 2(|V|V|−1) | |V | P|V |−1 P|V |−1 dG (v) |V1 | + i=3 i|Vi | i=1 i|Vi | 2> = = |V | |V | |V | P|V |−1 |V1 | + 3 i=3 |Vi | ≥ |V | P|V |−1 P|V |−1 |V | + 2 i=3 |Vi | 2 i=3 |Vi | = = 1+ |V | |V | P

v∈V

Hence we get, |V |−1

|V1 | +

X i=3

|V |−1

|Vi | = |V | > 2

X i=3

|V |−1

|Vi | =⇒ |V1 | >

X i=3

|Vi |.

This complete the answer. Exercise 1.19. Let G be a connected graph, and let r ∈ G be a vertex. Starting from r, move along the edges of G, going whenever possible to a vertex not visited so far. If there is no such vertex, go back along the edge by which the current vertex was first reached (unless the current vertex is r; then stop).(This procedure has earned those trees the name of depth-first search trees.) Show that the edges traversed in depth-first search form a normal spanning tree in G with root r . Proof. First notice that in dfs we always get a tree, since we always add a vertex to the current subgraph if it is not end point of any edge of current subgraph, so cannot create a cycle. To show it is spanning. Suppose it not spanning tree of G then there is a vertex v which is not in the tree but adjacent to a vertex u in the tree. But then when we left u for the last time we would have visited v instead of returning to r. So we get a contradiction that depth-first search completed. Hence we get a spanning tree, say T . To show T is normal. Last part remaining Exercise 1.23. Show that a graph is bipartite if and only if every induced cycle has even length. Proof. Recall. An induced cycle in G is a cycle in G forming an induced subgraph without any chords. 8

Rakesh Jana

IIT Guwahati

If a graph is bipartite then it does not have any odd cycle by proposition-1.6.1, hence does not have any induced cycle of odd length. To prove reverse part. Let us assume G is not bipartite. Since G is not bipartite so it has an odd cycle. Let C be a smallest odd cycle in G. Then C can not be induced cycle, since all induced cycle are even lengths. Then there exist x, y ∈ V (C) but xy ∈ / E(C). Thus we get two cycle C1 = xCyx, C2 = yCxy (traverse clockwise direction), among them one is odd and other is even. Hence we get a shorter odd cycle, a contradiction. This proves the result. Exercise 1.24. Find a function f : N → N such that, for all k ∈ N , every graph of average degree at least f( k) has a bipartite subgraph of minimum degree at least k . Proof. Define a map f : N → N by f (k) = 4k, ∀k ∈ N. The idea behind to consider this function is following: Every graph with an average degree of 4k have a subgraph H with minimum degree 2k, and we will lose another factor of 2 in moving H to its bipartite subgraph. Let H ∗ be the bipartite subgraph of H with the maximal number of edges. My claim is that H ∗ have minimum degree atleast k. If not, let v ∈ H ∗ such that dH ∗ (v) < k. This means v lost more then half of its neighbours in the process to form H to H ∗ . This means v is on the same partition with its looses neighbours. But in that case if we consider v in the other partition we can able to connect those previously looses vertices to v and form a new bipartite subgraph of H with more edges then H ∗ have, a contradiction. Hence it proves of my claim. Exercise 1.26. Prove or Disprove that every connected graph contains a walk that traverses each of its edges exactly once in each direction. Proof. Let W = v0 v1 · · · vk be a longest walk in G that traverses every edge exactly once in each direction. If possible let there exist a vertex v not visited by W . Without loss of any generality let us assume v ∈ N (vi ) for some 0 ≤ i ≤ k. Now consider a walk v0 W vi vvi W vk which is longer then W and also traverses each of its edges exactly once in each direction, a contradiction. So each vertex in G visited by W . Again suppose that W doesn’t contain all the edges, since W visits every vertex in G so G has an edge e = vi vj (i < j) not traversed by W . Consider a new walk v0 W vi vj vi W vk which is longer then W and also traverses each of its edges exactly once in each direction, a contradiction. So each edge in G visited by W . Hence every connected graph contains a walk that traverses each of its edges exactly once in each direction.

9

Rakesh Jana

2

IIT Guwahati

Matching, Covering and Packing

See some extra problem on Matching, Covering and Packing in the end( problem6.2.3 - problem-6.2.7). Exercise 2.2. Describe an algorithm that finds, as efficiently as possible, a matching of maximum cardinality in any bipartite graph. Proof. We already know that A matching M is maximum in a graph G if and only if there are no augmenting paths with respect to M. Let A and B be the bipartition of G, and let M be the matching in G, initially M = ∅ . Following algorithm known as Hungarian Method. Algorithm 1 Maximum-Matching (G, A, B, M ) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13:

if M saturates every vertex in A then stop; Let u be an an M-unsaturated vertex in A. Set S = {u}, T = ∅. if N (S) = T then |N (S)| < |S |, since |T | = |S| − 1 then by Hall’s theorem there is no matching that saturates every vertex in A then stop; Let v ∈ N (S) \ T . if v is M-saturated, let vw ∈ M then Set S = S ∪ {w}, T = T ∪ {v}; (Observe that |T | = |S| − 1 is maintained). goto step-5. Otherwise we get an M-augmenting u − v path. M = M△P = (M \ P ) ∪ (P \ M); (symmetric difference of the two sets of edges) Maximum-Matching (G, A, B, M )

Exercise 2.3. Show that if there exist injective function A → B and B → A between two infinite set A and B then there exist a bijection between A → B . Proof. The above problem is known as Cantor-Schrouder-Bernstein theorem. Although the statement seemingly obvious statement is surprisingly difficult to prove. The the strategy of the proof is following: Let f : A → B and g : B → A be two injective map. First, we apply f (A) = B1 ⊆ B. Next, g(B1 ) = A2 ⊆ A. Iterating this, we keep bouncing back and forth between 10

Rakesh Jana

IIT Guwahati

smaller and smaller subsets of A and B until the process stabilizes and we end up ¯ ⊆ A and B¯ ⊆ B for which f ( A) ¯ = B¯ and g( B) ¯ = A. ¯ This implies with some sets A ¯ ∼ B. ¯ The next task is to show that A \ A¯ ∼ B \ B. ¯ Finally, we conclude that A that A ∼ B. You can get complete proof of this result in the book Introductory Real Analysis by A. N. Kolmogorov and S. V. Fomin, 1st edition, Dover Publications. Exercise 2.4. Find an infinite counterexample to the statement of the marriage theorem. Proof. Let A = Z + ∪ {a} and B = Z + , here a is an alphabet. Let us consider a graph G with vertex set V (G) = A ∪ B, (consider A and B are different set). Let xy ∈ E(G), x ∈ A and y ∈ B if and only if x = y or x = a. Then for any S ⊆ A, |N (S)| ≥ |S|. But a matching saturating A must saturate Z + ⊆ A, and since these vertices have degree 1 and they already matched with every vertex in B , it cannot saturate a. Hence there is no matching saturating A. Exercise 2.5. Let k be an integer. Show that any two partitions of a finite set into k-sets admit a common choice of representatives. Proof. Let k ∈ N . Let X be a set of n elements with k|n and m = kn, and let A1 , · · · , Am and B1 , · · · , Bm are partitions of V into k-sets. Let us define a bipartite graph G with the vertex set V (G) = A ∪ B where A = {A1 , · · · , Am } and B = {B1 , · · · , Bm }, viewing each set Ai as a vertex. Let Ai Bj ∈ E(G) if and only if Ai ∩ Bj = 6 ∅. We want to apply Hall theorem. Let S ⊆ A and we have to estimate |N (S)|. Let S contain t many element of A. Then number of element of X contain in S is tk. Now number of element of B covering these tk element is atleast t, since each element Bj contains k elements. It follows that |N (S)| ≥ |S|. Hence Hall condition holds. Now by Halls theorem, we have a matching saturaing A, that is, we have a perfect matching. Therefore, any two partitions of a fin...