MTL1080: Tutorial 7
n2
1. Let G be a bipartite graph with n vertices and m edges. Show that m ≤ 4 .
2. Let G be a regular bipartite graph. Prove that G has a perfect matching.
3. Show that every closed odd walk contains an odd cycle. Using this property, prove that if a graph G contains
no odd cycles, then G is bipartite.
4. (a) Show that a bipartite graph G has a perfect matching if and only if |N (S)| ≥ |S| for all S ⊆ V .
(b) Give an example to show that this condition does not guarantee the existence of a perfect matching in
an arbitrary graph.
5. Show that every tree on n ≥ 2 vertices has at least one vertex of degree 1.
6. Prove or disprove: There is a unique path between any pair of distinct vertices of a tree G. Is the converse
true?
7. Is it true that if a simple graph has a Hamiltonian cycle, then it has a closed Eulerian walk?
8. How many Hamiltonian cycles are there in a complete graph with n ≥ 3 vertices?
9. For a simple graph G = (V, E), let ∆(G) = maxv∈V deg(v), and χ(G) denote the chromatic number of G.
Show that
χ(G) ≤ ∆(G) + 1.
10. (a) What is the chromatic number of the graph obtained from Kn by removing one edge?
(b) What is the chromatic number of the graph obtained from Kn by removing two edges with a common
vertex?
11. Define and prove the Euler formula for a disconnected planar graph with k components.
12. (a) If G is a planar graph with n ≥ 3 vertices and e edges, show that e ≤ 3n − 6.
(b) If G is a planar bipartite graph with n ≥ 3 vertices and e edges, show that e ≤ 2n − 4.
(c) Prove or disprove: The complete graph K5 and the complete bipartite graph K3,3 are planar.
13. Every planar graph contains a vertex having degree at most five.
14. A standard deck of 52 cards is dealt into 13 piles of 4 cards each. Prove that it is possible to select exactly
one card from each pile such that the 13 selected cards contain exactly one card of every rank (Ace, 2, 3, . . . ,
King).
15. Let G be a connected graph. Prove that G has an open Eulerian trail (a trail that traverses every edge exactly
once but starts and ends at distinct vertices) if and only if G has exactly two vertices of odd degree.
16. Show that the complete bipartite graph Km,n is Hamiltonian if and only if m = n ≥ 2. Furthermore, prove
that if an arbitrary bipartite graph G = (X ∪ Y, E) has a Hamiltonian path, then the sizes of the partite sets
satisfy |X| − |Y | ≤ 1.
17. Let G be a connected graph. Prove that an edge e ∈ E(G) is a bridge (a cut-edge) if and only if it does not
belong to any cycle in G.
18. Using the property established in Question 13 (that every planar graph contains a vertex of degree at most
5), prove by mathematical induction that every planar graph is 6-colorable.
19. Let G be a finite graph in which every vertex has a degree of at least 2. Prove that G contains a cycle.
1
20. The n-dimensional hypercube Qn is a graph whose vertices are the binary strings of length n, and two vertices
are adjacent if and only if their strings differ in exactly one bit.
(a) Prove that Qn is a bipartite graph for all n ≥ 1.
(b) For which values of n does Qn have an Eulerian circuit? Justify your answer.