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 graph below is not
Hamiltonian.
https://commons.wikimedia.org/w/index.php?curid=18988770
12. ([CLZ, Chapter 10, Q40]) Using Grinberg’s theorem, prove that the Herschel graph below is not
Hamiltonian.
https://commons.wikimedia.org/w/index.php?curid=10987060
MAST30011 Graph Theory
Problem Set 9
1. On April 1, 1975, Martin Gardner [puzzle master] published the following plane map and claimed
that it required five colours if adjacent countries were to receive distinct colors. Find a 4-colouring
of Gardner’s map.
2. Determine the chromatic number of the Petersen graph.
3. Prove that the chromatic number of a graph is equal to the maximum of the chromatic numbers
of its components.
4. Let G + H denote the join of graphs G and H. Prove that χ(G + H) = χ(G) + χ(H) for all G
and H.
5. Find a K4-free graph that is not 3-colourable. (Hint. How can you force two vertices to have the
same colour?)
6. Prove that if v is a cut-vertex in a graph G, then there are graphs G1 and G2 such that G = G1∪G2
and V (G1)∩ V (G2) = {v}, and conclude that the chromatic number χ(G) = max{χ(G1), χ(G2)}.
7. Assuming that the four colour theorem is true for all 2-connected planar graphs, prove that it is
true for all planar graphs.
8. Assuming that the four colour theorem is true for all 3-connected planar graphs, prove that it is
true for all planar graphs.
9. The obvious reason for a graph to have ‘large’ chromatic number is that it has a ‘large’ clique.
However, there are K3-free graphs (therefore with no large clique) that have arbitrarily large
chromatic number. Try to construct such a class of graphs. Hint. Consider the graph Gn with
V (Gn) = {(a, b) : 1 ≤ a < b ≤ n} where (a, b) is adjacent to (b, c) in Gn whenever 1 ≤ a < b <
c ≤ n. This graph is called a shift graph. (a) What is the largest clique in Gn? (b) Prove that for
all k there exists n such that χ(Gn) ≥ k.
10. An edge-colouring of a graph is an assignment of colours to its edges such that no two edges with
a common end-vertex receive the same colour. The least number of colours required is called the
edge-chromatic number (or chromatic index ) of the graph, denoted by χ′.
Show that χ′(T ) = ∆(T ) for any tree T .
11. ([CLZ, Chapter 14, Q5]) Prove that, for any connected graph G of order n and diameter d, we
have
χ(G) ≤ n− d+ 1.
12. ([CLZ, Chapter 14, Q4]) Let G be a k-chromatic graph and S a colour class from a proper k-
colouring of G, where k ≥ 2. Prove that there is a connected component H of G − S such that
χ(H) = k − 1.
13. ([CLZ, Chapter 14, Q19]) Let k ≥ 2 be an integer. For 1 ≤ i ≤ 2k + 1, let Gi be a copy of Kk.
Let G be the graph of order n = 2k2 + k obtained from vertex-disjoint union G1∪G2∪ · · · ∪G2k+1
by adding edges joining every vertex of Gi and every vertex of Gi+1 for all 1 ≤ i ≤ 2k + 1,
with subscripts modulo 2k + 1. Compute the bounds n/α(G), n − α(G) + 1 and ω(G) for χ(G).
Determine χ(G) and compare it with these bounds.
14. ([CLZ, Chapter 14, Q49]) Let G be a connected cubic graph with girth 3 (i.e. the length of a
shortest cycle has length 3) and order at least 5. Determine χ(G).
15. ([CLZ, Chapter 14, Q53(a)]) If H is a graph of order n and size n2/4, what bound does the general
bound χ(G) ≥ n2/(n2−2m) give about χ(H)? Show further that the bound χ(G) ≥ n2/(n2−2m)
is sharp.
Notes on Writing Proofs
Most theorems can be put into one of the following two forms, where A and B stand for
statements.
Theorem 1. If A then B. (or equivalently, “A implies B”).
Theorem 2. A if and only if B.
Equivalent form: contrapositive
To prove Theorem 1, you can prove it directly by assuming A and making some deductions
ending with B. Or you can prove the equivalent form, the contrapositive: “If B is false then
A is false.” Here “B is false” means that the negation of B is true.
Proving the contrapositive is indistinguishable from proof by contradiction.
Example. “Every bipartite graph has no odd cycles” can first be rephrased as
1: “Let G be a graph. If G is bipartite then G has no odd cycles.”
Then an equivalent set of statements is
2: “Let G be a graph. If G has at least one odd cycle then G is not bipartite.”
The if . . . then statement in 2 is the contrapositive of that in 1.
Note The negation of “G has no odd cycles” is “G has at least one odd cycle.” It is NOT
“All cycles of G are odd.”
The converse of Theorem 1 is “If B then A.” This is not equivalent to Theorem 1.
Theorem 2 is equivalent to the statement that Theorem 1 and its converse are both true.
To prove Theorem 2, we break the proof up into two parts: “if A then B” (or “A implies
B”) and “if B then A” (or “B implies A”).
Disproving by example
Show that “all graphs in a set S have property A” is false, all you have to do is come up
with one graph in S that does not have property A. For example, the converse of “if G is a
cycle then G is regular” is “if G is regular then G is a cycle”. To disprove this converse, the
graph K2 will do. It is 1-regular but is not a cycle.
Induction
Induction rests on the following principle: Let P (n) be a statement involving an arbitrary
integer n. Suppose both of the following statements have been proved for some integer n0:
(i) P (n0) is true;
(ii) if P (k) is true for all n0 ≤ k < n, then P (n) is true.
Then it can be concluded that P (n) is true for all integers n ≥ n0.
The statement “P (k) is true for all n0 ≤ k < n” is called the inductive hypothesis.
Note. This is a generalised version of mathematical induction. You may have seen a simpler
version before, where (ii) is “if P (n− 1) is true then so is P (n)”. The more general version
given here is needed for many proofs in graph theory.
See the example below for a proof by induction.
Proofs by maximality/minimality versus induction
We have seen several examples of proofs that proceed by choosing a maximal or minimal
object of a certain type (e.g. a shortest path, smallest connected subgraph etc). This is
usually equivalent to a proof by induction using contradiction.
Example. Here are two equivalent proofs of a theorem, one by maximality and one by
induction/contradiction.
Theorem. Every tree of order at least 2 has at least two end-vertices (vertices of degree 1).
The key idea in the following two proofs is essentially the same — if the end of a path in a
tree does not have degree 1 then the path can be lengthened. It is in the manner of making
use of this fact that the two proofs differ. In this example, the first proof is simpler and thus
preferable to the inductive proof which is induly complicated.
Proof 1 (using maximality). Let T be a tree of order at least 2. Let P be a longest path
in T . Let u and v be the first and last vertices of P . Let u′ be the next vertex in P after u.
(We know that P has at least two vertices, because T has order at least 2.)
Since P is a longest path, u is not adjacent in T to any vertex x not in P (otherwise P
could be extended by the edge xu, contradicting the assumption that it is a longest path).
Nor can u be adjacent to any vertex y on P other then u′. (For, if it were, the edge uy
together with the part of P from u to y would form a cycle, which contradicts the fact that
T is a tree and consequently has no cycles).
We deduce that the only neighbour of u in T is u′. Hence, u has degree 1 in T . For
similar reasons, v also has degree 1 in T . This proves the theorem.
Proof 2 (using induction). Let T be a tree of order at least 2. We proceed by contradiction:
assume that T has at most one vertex of degree 1. We prove by induction that
Claim. T contains a path of length k for all positive k.
(This is a contradiction, since clearly it cannot have a path longer than |V (T )|.)
For k = 1 the claim is clearly true: any two adjacent vertices define a path of length
1. So assume that n > 2 and that the statement is true for all k, 2 ≤ k < n. (Clearly,
we are using n0 = 2 in the framework of induction set out above.) Then by this inductive
hypothesis, there is a path P in T of length n− 1. Let u and v be the first and last vertices
of P . Let u′ be the next vertex in P after u. (We know that P has at least two vertices,
because n− 1 ≥ 2.)
By our assumption that T has at most one vertex of degree 1, either u or v must have
degree at least 2. Without loss of generality, assume it is u (otherwise, just consider v
instead). Since u has degree at least 2, it is adjacent to some vertex, say y, other than u′.
Now, y is not in P . (For, if it did, the edge uy together with the part of P from u to y would
form a cycle, which contradicts the fact that T is a tree and consequently has no cycles).
Thus, y is not on P . It follows that the edge yu, followed by the path P , is a path in T
of length equal to (length of P ) + 1 = n.
Thus, the claim is true for k = n. By induction, it is true for all n ≥ 2. As mentioned
above, this contradicts the fact that T is finite. So our assumption is false: T must have at
least two vertices of degree 1, and the theorem is proved by contradiction.