The University of Melbourne School of Mathematics and Statistics Semester 1, 2022 Graph Theory MAST30011 Subject Guide Subject Information Practical Class Problems Problem Sets Notes on Writing Proofs Subject Information 1 General Coordinator: Professor Sanming Zhou, School of Mathematics and Statistics, The Univer- sity of Melbourne, http://researchers.ms.unimelb.edu.au/~sanming@unimelb/. Contact Hours: 36 one-hour lectures (three per week) and 11 one-hour practical classes (one per week, starting in week 2). (However, we will lose one lecture due to Good Friday.) Assessment: Two written assignments due mid-semester and at the end of the semester amounting to a total of up to 50 pages (20% of assessment), and a 3-hour written examination in the examination period (80% of assessment). You will be examined on all topics covered in the lectures and practical classes. In all assessments, show all work that contributed to your answer. Marks will be awarded for clarity of presentation. Where asked to apply an algorithm, marks will be awarded for your description of the execution of the algorithm. Problem Sets: There are nine problem sets which are included in this guide. Answers/hints will be placed on http://www.lms.unimelb.edu.au/ approximately one week after the last topic on the sheets has been covered in lectures. Assignments: There are two assignments: Assignment 1 due 13:00pm Thursday 14 April 2022 Assignment 2 due 13:00pm Thursday 19 May 2022 Assignments should be submitted online via the Canvas LMS and will be marked using Gradescope grading platform. Late assignments will not be accepted unless accompanied by a medical certificate (or similar special consideration). Lectures: In 2022 this subject will be taught as dual delivery – a combination of on-campus and online teaching. Lecture capture will be published on the Canvas LMS after each lecture, and students who are unable to attend lectures in-person are required to watch lecture recordings in a timely fashion. Lectures will be held at the following times: 12:00–13:00 Tuesdays, PAR-Elisabeth Murdoch-G06 13:00–14:00 Thursdays, PAR-Redmond Barry-101 (Lyle Theatre) 12:00–13:00 Fridays, PAR-Elisabeth Murdoch-G06 Lectures will be given in the theatres above. However, in case of unforeseen circum- stances or changes in COVID-related regulations, we may switch to online lectures using Zoom video conferencing system. If this happens, you will be notified of the change of delivery mode through the Canvas LMS. Practical Classes: Starting in week 2, there will be eight practical classes each week, of which five will be on-campus and the other three will be online using Zoom video conferencing system. Details can be found in the timetable for this subject. Attend only one practical class each week, since all practical classes in the same week are repeats of each other. Prior to each practical class, complete the exercises listed later in this guide. In case of unforeseen circumstances or changes in COVID-related regulations, on- campus practical classes may be switched to online practical classes. If this happens, you will be notified of the change through the Canvas LMS. Consultations: Consultations will be available throughout the semester. Lecturer: – 16:15–17:15 Tuesdays, online, Zoom link will be put on the Canvas LMS – 14:15–16:15 Thursdays, online, Zoom link will be put on the Canvas LMS Tutors: Details for tutors’ consultation arrangements will be announced through the Canvas LMS. Website: Answers to problem sets and other course information are available on the Canvas LMS. See http://www.lms.unimelb.edu.au. Breadth options: This subject potentially can be taken as a breadth subject component for the following courses: Bachelor of Arts, Bachelor of Commerce, Bachelor of En- vironments, and Bachelor of Music. Read the breadth requirements for your degree at https://breadth.unimelb.edu.au/breadth/info/index.html, and discuss your choice with your student adviser before deciding on your subjects. Overview: Graphs model networks of all types such as telecommunication, transport, com- puter and social networks. They also model physical structures such as crystals and abstract structures within computer algorithms. This subject is an introduction to the modern field of graph theory. It emphasises the relationship between proving theorems in mathematics and the construction of algorithms to find the solutions of mathemat- ical problems within the context of graph theory. The subject provides material that supplements other areas of study such as operations research, computer science and discrete mathematics. Objectives: On completion of this subject, students should: be familiar with the definitions and basic theory of graphs, be able to prove simple results in graph theory, be able to apply many of the standard algorithms of graph theory. 2 Books The recommended text book is: G. Chartrand, L. Lesniak and P. Zhang, Graphs and Digraphs, 6th Edition, Chapman and Hall/CRC, 2015 At least four copies of this book are on seven day loan or overnight loan at the ERC Library. This book reinforces the lecture material, and contains many exercises, some of which may be used in the practical classes. In the lecture notes this book is referred to as [CLP] (e.g. [CLP, Theorem 3.2] means Theorem 2 in Chapter 3 in this book). Many other books are devoted to or have a large section on graph theory. Look for ones with graph theory or discrete mathematics in the title (around 511.5). Here are some titles. Graph Theory (R. Diestel) [recommended for advanced topics] Graphs – An Introductory Approach (R.J. Wilson and J.J. Watkins) Introduction to Graph Theory (R.J. Wilson) Graph Theory (J.A. Bondy and U.S.R. Murty) [recommended for advanced topics] Introduction to Graph Theory (D. B. West) 3 Subject Contents The number of lectures allocated to each part is an approximation. The actual time used may be shorter or longer than indicated. 1. Introduction [6 Lectures] Basic definitions Special families of graphs Subgraphs Walks, trails and paths Connected graphs, connected components and bridges Bipartite graphs Operations on graphs Isomorphisms and automorphisms Multigraphs and pseudographs 2. Distance in Graphs [3 Lectures] Distance in graphs Shortest paths and Dijkstra’s algorithm 3. Trees [4 Lectures] Trees Spanning trees Minimum spanning trees 4. Flows in Networks [3 Lectures] Directed graphs Maximum flows and minimum cuts Maximum flow algorithm 5. Connectivity [4 Lectures] Motivation Vertex connectivity Menger’s Theorem (vertex version) Whitney’s Theorem Edge connectivity Menger’s Theorem (edge version) Whitney’s inequalities Blocks Menger’s Theorems revisited 6. Matchings and Factors [4 Lectures] Matchings Matchings in bipartite graphs Tutte’s Theorem 7. Traversability [3 Lectures] Eulerian graphs Hamiltonian graphs Path and cycle exchanges Sufficient conditions 8. Planar Graphs [4 Lectures] Planar graphs Duality Euler’s formula Kuratowski’s Theorem Hamiltonian planar graphs Graphs on surfaces 9. Vertex Colouring [4 Lectures] 4-Colour Theorem Vertex colouring and chromatic number A greedy heuristic Brooks’ Theorem, and Szekeres-Wilf again 5-Colour Theorem Map Colour Theorem The conjectures of Hadwiger and Hajo′s * Reading Material: Eigenvalues of Graphs Most topics in this reading material will not be discussed in lectures, except that the definitions of the adjacency matrix and eigenvalues of a graph will be given in Part 1. Eigenvalues of graphs Diameter and eigenvalues Matrix-tree theorem Friendship graphs * Reading Material: More About Vertex Colouring Most topics in this reading material will not be discussed in lectures. A brief history of the 4-Colour Theorem On the proof of the 4-Colour Theorem Colour-critical graphs The conjectures of Hadwiger and Hajo′s Practical Class Problems The following questions must be attempted before each practical class. PSi-j refers to Question j in Problem Set i in this Subject Guide. For example, PS1-4 means Question 4 in Problem Set 1. Practical class 1: PS1-1, PS1-2, PS1-4, PS1-5, PS1-33 Practical class 2: PS1-18, PS1-20, PS1-32, PS1-36, PS1-37 Practical class 3: PS1-24, PS1-26, PS1-29, PS1-30, PS2-2 Practical class 4: PS3-2, PS3-3, PS3-4, PS3-8, PS3-9 Practical class 5: PS3-1, PS3-10, PS3-11, PS3-12 Practical class 6: PS4-2, PS4-4, PS5-3, PS5-4, PS5-6 Practical class 7: PS5-8, PS5-13, PS6-1, PS6-2, PS6-3 Practical class 8: PS6-5, PS6-6, PS6-6 from scratch (i.e. start with the empty matching), PS6-7, PS6-8 Practical class 9: PS7-1, PS7-2, PS7-3, PS7-5, PS7-7 Practical class 10: PS7-8, PS7-10, PS7-12, PS7-15, PS8-1 Practical class 11: PS8-2, PS8-3, PS8-4, PS8-5, PS9-10 Problem Sets There are nine problem sets. Roughly, Problem Set i corresponds to Part i of the lecture notes, for i = 1, 2, . . . , 9. No particular order is used for the questions in each problem set. You are required to work through all questions in these problem sets. MAST30011 Graph Theory Problem Set 1 1. Draw the multigraph that represents the Hampton Court Maze shown below. Have one vertex for the start, one vertex for the destination, one vertex for each location where there are three different places to walk, and one vertex for each dead-end. How many vertices are there. Have one edge for each passage that joins two locations. How many edges are there Write down the degree of each vertex. What is the degree sequence of the graph How many paths are there from the start to the destination 2. How many edges are there in each of the following graphs: (a) the complete graph K10 (b) the complete bipartite graph K4,9 (c) the hypercube Q4 (d) the wheel W8 (e) the Petersen graph 3. Can a graph of order 30 have three vertices of degree 4 and the rest of degree 3 What about a multigraph 4. Let G be a graph which contains m vertices of degree m and n vertices of degree n. Prove that if G contains an odd vertex, then every vertex of G is odd. 5. Prove that every set of six people contains (at least) three mutual acquaintances or three mutual strangers. Is it true that every set of five people has this property How can this result be generalised (Hint #1. Model using a graph. Hint #2. Consider the acquaintances or strangers (whichever set is larger) of one particular person.) 6. Can a multigraph of order 3 have degree sequence 8, 3, 3 Give reasons. 7. A graph of order 7 and with 10 edges has six vertices of degree a and one of degree b. What are a and b 8. Draw a graph G with V (G) = {a, b, c, d, e} and E(G) = {ab, ac, ad, bd, ce, eb}. Draw a 3-regular graph of order 6 which has G as a subgraph. 9. Prove that if G is regular then G is regular. 10. Prove that every k-regular graph with girth 4 has at least 2k vertices. (The girth of a graph is the length of a shortest cycle.) 11. In the graph on the right, find a walk of shortest length which covers each edge at least once. Also find a longest path in this graph, a longest trail, a shortest cycle and a longest cycle. a b c d ef g h 12. Write a formula for the number of edges in the product G2H in terms of the number of vertices and edges in G and H. 13. (CLZ, Chapter 1, Q4) A graph G has order n = 3k + 3 for some positive integer k. Every vertex of G has degree k + 1, k + 2 or k + 3. Prove that G has at least k + 3 vertices of degree k + 1 or at least k + 1 vertices of degree k + 2 or at least k + 2 vertices of degree k + 3. 14. (CLZ, Chapter 1, Q5) Suppose that the degree of every vertex of a graph G is one of three consecutive integers. Suppose further that for each degree x, the graph G contains exactly x vertices of degree x. Prove that two-thirds of the vertices of G has odd degree. 15. (CLZ, Chapter 1, Q11) Show that if G is a non-regular graph of order n and size rn/2 for some integer r with 1 ≤ r ≤ n 2, then (G) δ(G) ≥ 2. 16. Find all bridges in the graph on the right. a b c d e f g h j k l m n 17. Let G be the graph with vertex set {1, 2, . . . , 15} in which i and j are adjacent if and only if their greatest common factor exceeds 1. Count the components of G and determine the maximum length of a path in G. 18. Let G be a graph. Let S(G) be the subdivision of G obtained by replacing each edge e = uv of G by a new vertex ve, and joining ve to u and v. Show that if G is any nontrivial graph, then S(G) is bipartite. 19. Prove that a graph G is connected if and only if for every two vertices u and v of G there exists a u-v walk in G. 20. Let G be a graph with the property that every edge joins an even vertex and an odd vertex. Prove that G is bipartite. 21. (CLZ, Chapter 2, Q26) Prove that a nontrivial graph is bipartite if and only if it contains no induced odd cycle. (It is allowed to use the characterisation of bipartite graphs in the lecture notes.) 22. Prove that every graph G contains a bipartite subgraph with at least half as many edges as G. 23. Show that the following two graphs are isomorphic, by finding an appropriate isomorphism. ab c de f g h j k a b c de f g h j k 24. Show that the following two graphs are not isomorphic. a b c d e f g h a b c d e f g h 25. Find another graph G of order 5 (besides the 5-cycle) such that G ～= G. 26. Draw all the nonisomorphic 3-regular graphs of order 6. (Hint : Consider their complements.) 27. Draw all the nonisomorphic 4-regular graphs of order 6. (Hint : Consider their complements.) 28. Determine which of H1, H2 and H3 are subgraphs of the following graph G. Which are induced subgraphs of G Which are isomorphic to subgraphs of G Which are isomorphic to induced subgraphs of G a b c e a b c d ef G: H1: H2: H3: a b f c a b c e 29. How many distinct graphs are there with vertex set {1, 2, . . . , n} How many distinct graphs are there with vertex set {1, 2, . . . , n} and m edges For these questions, what happens if “with vertex set {1, 2, . . . , n}” is replaced by “with n vertices” 30. (CLZ, Chapter 1, Q20) Show for each integer n ≥ 2 that, up to isomorphism, there is exactly one bipartite graph of order n having size bn2/4c. Show further that this graph achieves the maximum size among all bipartite graphs of order n. 31. (CLZ, Chapter 1, Q9(a)) Let G and H be two isomorphic graphs where one or more vertices of G (and H) have degree r. Let S be the set of vertices of degree r in G and T the set of vertices of degree r in H. Prove that G[S] ～= H[T ]. 32. Prove that the spectrum of Kn is ((n 1)1, ( 1)n 1). 33. Let P3 be the path of length 2. Compute the characteristic polynomial φP3(x) and determine the spectrum of P3. 34. Let Cn be the cycle of length n ≥ 3. Compute the spectrum of Cn. 35. Prove that a graph G is regular (of degree r) if and only if the all-1 vector (1, . . . , 1) is an eigenvector of G (with corresponding eigenvalue r). 36. Prove that if |V (G)| ≥ 2 and G is disconnected then G is connected. 37. Recall that δ(G) is the minimum degree of a vertex of G. (a) Prove that every graph G with order n and δ(G) ≥ (n 1)/2 is connected. (b) Prove that this result is best possible by finding, for every even integer n ≥ 2, a disconnected graph G of order n with δ(G) = (n 2)/2. MAST30011 Graph Theory Problem Set 2 1. Let G be the following weighted graph. a c e b d f 28 2 2 6 3 4 5 9 4 8 3 g h 3 Use Dijkstra’s algorithm to find shortest paths in G from a to all other vertices of G. Present the paths in the form of a tree T (such that the shortest path from a to v is the av-path in T , for all v). 2. Let G be the following weighted graph. a b c d e f g 1 4 13 5 6 7 11 5 8 86 3 Apply Dijkstra’s algorithm to find the distance from a to all other vertices of G. State what the labels of vertices are when each new vertex is chosen to add to the set S. Finally, give a tree determining shortest paths from a to all other vertices of G. 3. Prove that Dijkstra’s algorithm is correct; that is, when the algorithm terminates, the label `(v) of each vertex v is the length of a shortest path from u0 to v. 4. (CLZ, Chapter 2, Q14) Prove that a graph G is connected if and only if for every partition {V1, V2} of V (G), there exists an edge of G joining a vertex of V1 and a vertex of V2. 5. (CLZ, Chapter 2, Q16) Let G be a disconnected graph of order n ≥ 6 having three connected components. Prove that (G) ≥ 2n 3 . 6. (CLZ, Chapter 2, Q20) Let G be a nontrivial connected graph that is not bipartite. Prove that G contains two adjacent vertices u and v such that deg(u) + deg(v) is even. 7. (CLZ, Chapter 2, Q23) Prove that if G is a connected graph of order n ≥ 2, then the vertices of G can be listed as v1, v2, . . . , vn such that each vertex vi (2 ≤ i ≤ n) is adjacent to at least one vertex in the set {v1, v2, . . . , vi 1}. MAST30011 Graph Theory Problem Set 3 1. Let d1, . . . , dn be positive integers (n ≥ 2). Prove that there is a tree with degrees d1, . . . , dn if and only if ∑ i di = 2n 2. 2. Find four spanning trees in the graph on the right. 3. Prove that every graph of order n with m edges contains at least m n + 1 cycles. 4. Let T be a tree with maximum vertex degree 3. What is the relationship between the number of degree-1 vertices and the number of degree-3 vertices in T First, draw small examples to find the relationship. Then prove your answer using the Handshaking Theorem. Then try to find an inductive proof. 5. How many edges must be removed from a connected 4-regular graph G of order 20 to obtain a spanning tree of G 6. A forest is a graph with no cycles. Prove that if G is a forest then k(G) = |V (G)| |E(G)|. 7. A saturated hydrocarbon (also called alkane or paraffin) is a molecule formed from carbon and hydrogen atoms by adding bonds between atoms such that each carbon atom is in four bonds, each hydrogen atom is in one bond, and no sequence of bonds forms a cycle of atoms. If there are c carbon atoms and h hydrogen atoms, prove that h = 2c + 2. In Questions 8 and 9 below, G is the following weighted graph. a c e b d f 23 2 2 3 4 4 5 3 8. Use Kruskal’s algorithm to find a minimum spanning tree T of G. What is the weight of T 9. Use the Prim-Jarnik algorithm to grow a minimum spanning tree Ta of G from the vertex a, and another, Tb, from b. 10. Let G be a connected weighted graph. Suppose that G has two different minimum spanning trees. Prove that G has at least two edges of the same weight. (Hint. Order the edges of the trees in increasing weight, and consider the first edge that is in one tree but not the other.) 11. Using the definition or a known characterization of a tree, prove the following statements: (a) Suppose that G is not a complete graph. Prove that G is a tree if and only if adding any edge with end-vertices in V (G) creates exactly once cycle. (b) A graph G is a tree if and only if it is loopless (i.e. without any edge from a vertex to itself) and has exactly one spanning tree. 12. Prove that every tree other than a path with at least 4 vertices has at least 3 leaves (vertices of degree 1). 13. (CLZ, Chapter 3, Q30) A vertex v of a graph G is called a central vertex if its eccentricity is equal to the radius of G, that is, ecc(v) = rad(G). The centre of G, denoted by Cen(G), is the subgraph of G induced by the set of central vertices. Now let T be a tree of order at least 3, and let T ′ be the tree obtained from T by deleting all its leaves (pendant vertices). (a) Show that diam(T ) = diam(T ′) + 2, rad(T ) = rad(T ′) + 1 and Cen(T ) = Cen(T ′). (b) Use the result in (a) to prove that Cen(T ) is either K1 or K2. The tree T is called central or bicentral, respectively, in these two cases. (c) Show that a tree T is central or bicentral according to whether diam(T ) = 2 rad(T ) or diam(T ) = 2 rad(T ) 1. 14. (CLZ, Chapter 3, Q41) Let P : u0, u1, . . . , ut be a longest path in a tree T . Show, for every vertex u in T , that ecc(u) = max{dist(u, u0), dist(u, ut)}. MAST30011 Graph Theory Problem Set 4 1. Consider the following networks. a 1 8 2 5 c b e 4 d4 x y 7 9 5 96 a 2 4 4 5 b d e 1 c 1 x y 4 1 5 1 (i) (ii) (a) Find a minimum cut in each network by inspection. (b) Consider the network in (i). Find a maximum flow using the labelling algorithm, making sure that the first unsaturated path is x, a, c, y. From the results of the algorithm, determine a minimum cut in the network. Then repeat, using the first path x, a, d, e, y. (c) Find a maximum flow in the network (ii) using the labelling algorithm and hence determine a minimum cut in the network. (d) Find a cut of capacity 34 in network (i). 2. The following network N has source x and sink y with arc capacities as shown. (a) Use the labelling algorithm to find a maximum flow f in N . Show at least three stages of the algorithm, and state the value of the maximum flow. (b) Find a minimum cut in N . 3. Use the labelling algorithm to verify that if the capacities of the arcs of a network are integers, then there is a maximum flow such that the flow on each arc is an integer. 4. Let N be the network shown below, where each arc has unlimited capacity. Note that the under- lying digraph of N is weakly connected (i.e. there exists a path between any two vertices) and that every vertex, except possibly the source and sink, has positive indegree and positive outdegree. Show that there is no flow in N such that the flow along every arc is positive. s N: t 5. ([CLZ, Chapter 8, Q13(b)]) Let N = (V,A) be a network with capacity c. Suppose that +(S) is a minimum cut in N . Prove that any two maximum flows in N agree on both +(S) and (S), where (S) = {wz ∈ A : w ∈ V S, z ∈ S}. (More specifically, prove that for any two maximum flows f1, f2 in N , we have f1(uv) = f2(uv) for any uv ∈ +(S) and f1(wz) = f2(wz) for any wz ∈ (S).) MAST30011 Graph Theory Problem Set 5 1. Find all cut-vertices in the graph on the right. a b c d e f g h j k l m n 2. Find a counterexample to each of the following statements: (a) If G is a connected graph that contains only vertices of even degree, then G contains no cut-vertices. (b) If G is a connected graph such that every vertex of G lies on a cycle of G, then G contains no cut-vertices. (c) If G is a connected graph with a cut-vertex, then G contains a bridge. 3. (Mantel’s Theorem 1907) A graph is triangle-free if it contains no K3-subgraph. What is the maximum number of edges in a triangle-free graph with n vertices (Hint. first guess the triangle-graph with the maximum number of edges. Second, calculate the number of edges in this graph. Third, prove that every triangle-free graph has at most this many edges. Is you example the only triangle-free graph with the maximum number of edges.) Answer the same question for graphs with no Kt-subgraph for any integer t ≥ 3 (Tura′n’s Theorem). 4. Let G be a connected graph with at least three vertices. Let G′ be the graph obtained from G by adding an edge joining x, y whenever distG(x, y) = 2. Prove that G ′ is 2-connected. 5. Let G be a k-connected graph of order n and diameter d. Show that n ≥ k(d 1) + 2 by using Menger’s Theorem. 6. For each integer ` ≥ 1, give an example of a graph G` with connectivity κ(G`) = 1 and edge- connectivity λ(G`) = `. (Hint. Start with ` = 2.) 7. A Θ-graph consists of three internally vertex-disjoint paths joining two vertices (because such a graph looks like Θ). Characterise the graphs with no Θ-subgraphs What is the maximum number of edges in a graph with n vertices and no Θ-subgraphs (Hint. First consider these questions for 2-connected graphs. Then for a general graph, consider its blocks, that is, maximal 2-connected subgraphs.) 8. Show that if G is a connected graph of order at least 2 that contains a bridge, then either G has order 2 or G contains cut-vertices. 9. ([CLZ, Chapter 4, Q1]) A graph is called a complete k-partite graph if its vertex set can be partitioned into k nonempty parts such that any two vertices in the same part are nonadjacent and any two vertices in distinct parts are adjacent. Determine the connectivity and edge-connectivity of any complete k-partite graph. 10. ([CLZ, Chapter 4, Q2]) Let G be a k-connected graph and let v1, v2, . . . , vk be k distinct vertices of G. Let H the graph obtained from G by adding a new vertex w and k new edges joining w and v1, v2, . . . , vk, respectively. Prove that κ(H) = k by using Menger’s theorem and Whitney’s inequalities. 11. ([CLZ, Chapter 4, Q21]) Let G be a k-connected graph and let S and T be nonempty disjoint subsets of V (G). Prove that there exist k internally vertex-disjoint paths P1, P2, . . . , Pk in G such that each of them is a (u, v)-path for some u ∈ S and v ∈ T (but the pairs (u, v) may be different for different paths) and |V (Pi) ∩ S| = |V (Pi) ∩ T | = 1. 12. ([CLZ, Chapter 4, Q25]) Let G be a k-edge-connected graph and let S and T be nonempty disjoint subsets of V (G). Prove that there exist k edge-disjoint paths P1, P2, . . . , Pk in G such that each of them is a (u, v)-path for some u ∈ S and v ∈ T (but the pairs (u, v) may be different for different paths) and |V (Pi) ∩ S| = |V (Pi) ∩ T | = 1. 13. Let v be a vertex of a connected graph G. Prove that v has a neighbour in every connected component of G v. Conclude that no graph has a cut-vertex of degree 1. MAST30011 Graph Theory Problem Set 6 1. Find a cubic graph with no perfect matching. 2. Take two disjoint paths P4 and P5 of lengths 3 and 4 respectively, and add an edge from each vertex of one to each vertex of the other. Does the resulting graph have a perfect matching 3. Let G be the following graph: a c b d e g f h (a) Consider the matching M = {gd, ah} in G. Find an augmenting path for M in G. Use this path to find a matching of cardinality 3 in G. What is the cardinality of a maximum matching in G Give a reason for your answer. (b) Apply the algorithm given in lectures, from the start, to find a maximum matching in G. 4. Here is a theorem of Hall. A collection {S1, . . . , Sn} of finite nonempty sets is said to have a system of distinct representatives if there exists a set {s1, . . . sn} of distinct elements such that si ∈ Si for 1 ≤ i ≤ n. Hall’s theorem states that a system of distinct representatives exists if and only if, for each k (1 ≤ k ≤ n), the union of any k of these sets contains at least k elements. Define a bipartite graph G where V1 is {S1, . . . , Sn} and V2 is the set of elements of the union of Si over 1 ≤ i ≤ n, with an edge from Si to x ∈ V2 iff x ∈ Si. Prove Hall’s theorem by considering matchings in G. 5. A vertex cover of a graph G is a set X V (G) such that each edge of G is incident with at least one vertex in X (that is, vertices in X cover E(G)). Prove the following Ko¨nig-Egerva′ry Theorem: If G is a bipartite graph, then the maximum size of a matching in G is equal to the minimum size of a vertex cover of G. 6. Let G be the following graph: a c b d h j i k e f g m n p Assume the matching algorithm given in lectures finds the matching M = {ah, bi, cj, dk, em} in G after 5 steps. Complete the algorithm and hence find a maximum matching. 7. The complete graph K2n+1 has no perfect matching since it has an odd number of vertices. Con- vince yourself that the complete graph K2n has perfect matchings. How many perfect matchings are there in K2n 8. ([CLZ, Chapter 12, Q1]) Prove that every tree has at most one perfect matching. 9. ([CLZ, Chapter 12, Q5]) Let G be a bipartite graph with bipartition {A,B} such that |A| = |B| = k. Let m be the size of G. (a) Prove that if m ≥ k2 k + 1, then G has a perfect matching. (b) Give an example to show that G may not contain a perfect matching if m = k2 k. 10. ([CLZ, Chapter 12, Q17(a)]) Let G be a graph in which every vertex has odd degree. Let {V1, V2} be a partition of V (G). Denote by [V1, V2] the set of edges of G joining V1 and V2. Prove that |V1| and |[V1, V2]| have the same parity. 11. ([CLZ, Chapter 12, Q17(b)]) Prove that every (2k + 1)-regular, 2k-edge-connected graph, k ≥ 1, contains a 1-factor. MAST30011 Graph Theory Problem Set 7 1. For which values of n is Kn eulerian Why 2. What is the minimum number of edges which must be added to a 5-regular graph of order 40, in order to make a graph with an eulerian trail 3. Prove that CmCn is eulerian for all m,n ≥ 3. 4. Suppose G is a connected graph with exactly 2k vertices of odd degree. Show that the edges of G can be covered using k trails, no two of which share an edge. 5. Show that a connected multigraph G is eulerian if and only if the edge set of G can be partitioned into subsets, each of which induces a cycle (where 2-cycles are permitted). 6. A tournament is a directed graph such that for any two distinct vertices x and y, precisely one of the arcs (x, y) and (y, x) is present in the graph. Prove that in any tournament there exists a directed path containing all the vertices. (A tournament models a ‘round-robin tournament’ in an obvious way. The result above says that we can always rank the players in a linear order x1, x2, . . . , xn (where n is the number of vertices) such that x1 beats x2, x2 beats x3, and so on. But this does not mean that each player beats all those that follow in the sequence.) 7. Prove that if δ(G) ≥ 2 then G contains at least one cycle. 8. ([CLZ, Chapter 6, Q2]) Show that if G is a graph containing a vertex that is adjacent to at least three vertices of degree 2, then G is not Hamiltonian. 9. ([CLZ, Chapter 6, Q3(a)]) Show that if G is a bipartite graph of odd order, then G is not Hamil- tonian. 10. ([CLZ, Chapter 6, Q11]) Show that the bound in the Chva′tal-Erdo¨s Theorem is sharp by proving that the graph G = Kk,k+1 (where k ≥ 2) satisfies κ(G) = α(G) 1 but is not Hamiltonian. 11. ([CLZ, Chapter 6, Q15(a)]) Prove that Kr,2r,3r is Hamiltonian for any positive integer r 12. ([CLZ, Chapter 6, Q15(b)]) Prove that Kr,2r,3r+1 is non-Hamiltonian for any positive integer r 13. ([CLZ, Chapter 6, Q21]) The toughness of a noncomplete graph G, denoted by t(G), is defined to be the maximum real number t such that G is t-tough. In other words, t(G) = min { |S| k(G S) } , where the minimum is taken over all vertex cuts S of G. Prove that for any noncomplete graph G and any spanning subgraph H of G, we have t(H) ≤ t(G). 14. ([CLZ, Chapter 6, Q7]) Let G be a graph with order n ≥ 3 such that for every vertex v ∈ V (G) there is a Hamilton path of G with initial vertex v. (a) Prove that G is 2-connected. (b) Is it true that G is always 3-connected (c) Give an example to show that G is not necessarily Hamiltonian. 15. The m× n rectangular grid Gm,n (where m,n ≥ 1 are integers) can be defined as follows: V (Gm,n) = {(i, j) : i, j are integers, 1 ≤ i ≤ m, 1 ≤ j ≤ n} E(Gm,n) = {uv : u = (i, j) ∈ V (Gm,n), v = (i′, j′) ∈ V (Gm,n), |i i′|+ |j j′| = 1}. Prove that Gm,n is Hamiltonian if and only if either m or n is even. 16. Let G be a Hamiltonian bipartite graph with order 8. (a) Prove that δ(G) ≥ 2 and (G) ≤ 4. (b) Assume further that G is eulerian and (G) = 4. What can be said about the structure of G MAST30011 Graph Theory Problem Set 8 1. (a) Find a simple planar graph with degree sequence (4, 4, 4, 4, 3, 3). (b) Find a simple non-planar graph with the same degree sequence. 2. Is the following graph planar Is it maximal planar Remove or add edges to it to make it maximal planar. 3. Draw a 5-regular simple planar graph. What is the minimum number of vertices in such a graph What is the maximum number of vertices in such a graph 4. Prove that the Petersen graph is nonplanar by using the fact that every cycle of it has length ≥ 5. 5. (a) Let G be a simple planar graph with n vertices and m edges. Show that if a shortest cycle in G has length k, then m ≤ k(n 2)/(k 2). (b) Deduce that a simple planar bipartite graph of order n ≥ 1 has at most 2n 4 edges. 6. A graph is toroidal if it can be drawn in a torus without crossings. What is the largest toroidal complete graph Hint. It may help to think of the torus as a square with opposite sides identified. 7. Prove that every simple planar graph can be drawn with straight edges and no crossings. 8. ([CLZ, Chapter 10, Q1]) Prove that a simple graph is planar if and only if each of its blocks is planar. 9. ([CLZ, Chapter 10, Q2]) Prove that if G is a simple plane graph with n vertices, m edges, f faces, then n m + f = 1 + k(G), where k(G) is the number of connected components of G. 10. ([CLZ, Chapter 10, Q7]) Let G be a simple graph with order n ≥ 6. Suppose that G contains three spanning trees such that every edge of G belongs exactly one of these three trees. Prove that G is nonplanar. 11. ([CLZ, Chapter 10, Q39]) Using Grinberg’s theorem, prove that the Grinberg
