MA010 Tutorial 5
Fr´ed´eric Dupuis
This tutorial covers material from lecture 6.
Problem 1
Prove that the following two graphs are not 3-colourable. Are they 4-colourable?
a
f
g
ec
b
d
paq
a
f
b
c
d e
k
g
h
i j
pbq
Source: https://www.math.ucdavis.edu/˜greg/145/hw6sol.pdf
Problem 2
Let G be a graph with chromatic number χpGq ě 11 and girth g ě 11 (the girth is the
length of the shortest cycle). Prove that the number of vertices of G is bigger than 10 ¨ 94.
(Hint: Remember Lemma 6.10 from class: every graph G has a subgraph of minimum degree
ě χpGq ´ 1.)
Source: www.tau.ac.il/˜nogaa/graphs134h.pdf
Problem 3
Let G “ pV, E1 Y E2q be a graph, where E1 and E2 are nonempty matchings. Show that
the chromatic number of G is 2.
Source: www.tau.ac.il/˜nogaa/graphs134h.pdf
1
Problem 4
Show that the complete bipartite graph K2,4 is not 2-choosable (i.e. 2-list-colourable).
That is, assign a list of two colours to every vertex such that no proper colouring of the
vertices by colours from their list exists.
K2,4
2