Notes on Graph Theory
Maris Ozols
June 8, 2010
Contents
0.1 Berges Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
0.2 K
onigs Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
0.3 Halls Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
0.4 Tuttes Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
0.5 Mengers Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
0.6 Kuratowskis Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
0.7 Five Colour Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
0.8 Brooks Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
0.9 Hajos Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
0.10 Vizings Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
0.11 Tur
ans Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
1
0.1 Berges Lemma
Lemma (Berge, 1957). A matching M in a graph G is a maximum matching if and only if G has no
M -augmenting path.
Proof. Let us prove the contrapositive: G has a matching larger than M if and only if G has an M -augmenting
path. Clearly, an M -augmenting path P of G can be used to produce a matching M 0 that is larger than
M just take M 0 to be the symmetric difference of P and M (M 0 contains exactly those edges of G that
appear in exactly one of P and M ). Hence, the backward direction follows.
For the forward direction, let M 0 be a matching in G larger than M . Consider D, the symmetric difference
of M and M 0 . Observe that D consists of paths and even cycles (each vertex of D has degree at most 2 and
edges belonging to some path or cycle must alternate between M and M 0 ). Since M 0 is larger than M , D
contains a component that has more edges from M 0 than M . Such a component is a path in G that starts
and ends with an edge from M 0 , so it is an M -augmenting path.
2
0.2 K
onigs Theorem
Theorem (K onig, 1931). The maximum cardinality of a matching in a bipartite graph G is equal to the
minimum cardinality of a vertex cover of its edges.
|C| |M |
Trivial: One needs at least |M | vertices to cover all edges of M .
|C| |M |
Choose cover: For every edge in M choose its end in B if some alternating path ends there, and its
end in A otherwise.
Pick edge: Pick ab E. If ab M , we are done, so assume ab
/ M . Since M is maximal, it cannot
be that both a and b are unmatched.
Alternating path that ends in b:
Easy case: If a is unmatched, then b is matched and ab is an alternating path that ends in B,
so b C.
Hard case: If b is unmatched, then a is matched to some b0 . If a / C, then b0 C and some
alternating path P ends in b . If b P , let P = P b, otherwise P = P b0 ab. M is maximal, so P 0
0 0 0
is not an augmenting path, so b must be matched and hence b C, since P 0 ends at b.
3
0.3 Halls Theorem
Theorem (Hall, 1935). A bipartite graph G contains a matching of A if and only if |N (S)| |S| for all
S A.
=
Trivial: If A is matched then every S A has at least |S| neighbours.
=
Induction on |A|: Apply induction on |A|. Base case |A| = 1 is trivial.
Many neighbours: Assume |N (S)| |S| + 1 for every S 6= . By induction hypothesis G e has a
matching M , where e E can be chosen arbitrarily. Then M {e} is a matching of A.
Few neighbours: Assume |N (S)| = |S| for some S
/ {, A}.
Cut in two pieces: Consider graphs GS and GA\S induced by S N (S) and (A\S)(B \N (S)),
respectively.
Check marriage condition: It holds for both graphs:
We kept all neighbours of S, so |NGS (S)| = |NG (S)|.
If NGA\S (S 0 ) < |S 0 | for some S 0 A \ S, then |NG (S S 0 )| = |NG (S)| + NGA\S (S 0 ) <
|S| + |S 0 |, a contradiction.
Put matchings together: By induction hypothesis GS and GA\S contain matchings for S and
A \ S, respectively. Putting these together gives a matching of A in G.
4
0.4 Tuttes Theorem
Theorem (Tutte, 1947). A graph G has a 1-factor if and only if q(G S) |S| for all S V (G), where
q(H) is the number of odd order components of H.
=
Trivial: If G has a 1-factor, then Tuttes condition is satisfied.
=
Consider an edge-maximal counterexample G: Let G be a counterexample (G satisfies Tuttes
condition, but has no 1-factor). Addition of edges preserves Tuttes property, so it suffices to consider
an edge-maximal counterexample G (adding any edge yields a 1-factor).
G has no bad set: We call S V bad if s S, v V : sv E and all components of G S are
complete. If S is a bad set in a graph with no 1-factor, then S or violates Tuttes condition. Thus,
G has no bad set.
Choose S 0 : Let S 0 = {v V : v is adjacent to all other vertices}. Since S 0 is not bad, G S 0 has a
component A with non-adjacent vertices a, a0 .
Define a, b, c, d: Let a, b, c A be the first 3 vertices on the shortest a a0 path within A (ab, bc E
but ac
/ E). Moreover, since b / S 0 , there exists d V such that bd
/ E.
Even cycles containing ac and bd: G is edge-maximal without 1-factor, so let Mac and Mbd be
1-factors of G + ac and G + bd, respectively. Mac Mbd consists of disjoint even cycles, so let Cac and
Cbd be the cycles containing ac and bd, respectively.
Contradiction by constructing a 1-factor:
If ac
/ Cbd then Mbd Cbd is a 1-factor of G.
If ac Cbd then Mbd is a 1-factor of G, where = bd . . . is the shortest cycle whose vertices
are all in Cbd and the last edge being either ab or cb. In particular, ac
/ E().
5
0.5 Mengers Theorem
Theorem (Menger, 1927). Let G = (V, E) be a graph and A, B V . Then the minimums number of
vertices separating A from B in G is equal to the maximum number of disjoint A B paths in G.
min separator max # of paths
Trivial: To separate A from B one must cut every A B path .
min separator max # of paths
Induction on |E|: Apply induction on |E|. Let k be the size of a minimal A B separator. If E =
then |A B| = k and there are k trivial paths.
Find a separator containing an edge: |E| 1, so G has an edge e = xy. First find an A B
separator containing adjacent vertices.
Contract e: If G contains less than k disjoint A B paths, then so does G/e. Let ve be the
vertex obtained by contracting e.
Find a smaller separator: Let Y be a smallest A B separator in G/e. It must be the case
that |Y | is either k 1 or k:
A minimal A B separator in G is also an A B separator in G/e, so |Y | k.
If |Y | k 2 then G has an A B separator of size k 2 (if ve
/ Y ) or k 1 (if ve Y ), a
contradiction.
If |Y | = k, by induction hypothesis there exist k disjoint A B paths and we are done. Thus,
|Y | = k 1. Also, ve Y since otherwise Y would be an A B separator in G of size less than k.
Extend the separator: X = (Y \ {ve }) {x, y} is an A B separator in G of size k, containing
edge e = xy.
Remove the edge and apply induction hypothesis: To apply the induction hypothesis, consider
G e. Use X as one of the sets A, B.
A X paths: Every A X separator in G e is also an A B separator in G and hence contains
at least k vertices. By induction hypothesis there are k disjoint A X paths in G e
X B paths: Similarly.
Combine paths: X separates A and B in G, so these two paths systems do not meet outside of
X and thus can be combined into k disjoint A B paths.
6
0.6 Kuratowskis Theorem
Theorem (Kuratowski, 1930; Wagner, 1937). The following assertions are equivalent:
1. G is planar;
2. G contains neither K5 nor K3,3 as a minor;
3. G contains neither K5 nor K3,3 as a topological minor.
Kuratowskis theorem follows from these lemmas:
Lemma (2 3). A graph contains K5 or K3,3 as a minor if and only if it contains K5 or K3,3 as a
topological minor.
Lemma (3-connected case). Every 3-connected graph without a K5 or K3,3 minor is planar.
Lemma. If |G| 4 and G is edge-maximal without K5 and K3,3 as topological minors, then G is
3-connected.
Lemma (2 3). A graph contains K5 or K3,3 as a minor if and only if it contains K5 or K3,3 as a
topological minor.
=
Trivial: Every topological minor is also a minor.
=
Trivial for K3,3 : Every minor with maximum degree at most 3 is also a topological minor.
Remaining part: It suffices to show that every graph G with a K5 minor contains K5 as a topological
minor or K3,3 as a minor.
7
Lemma (3-connected case). Every 3-connected graph without a K5 or K3,3 minor is planar.
Induction on |V |: Apply induction on V . If |V | = 4 then G = K4 , which is planar.
Contract edge xy: G has an edge xy such that G/xy is again 3-connected. Moreover, G/xy has no
K5 and no K3,3 minor. By induction hypothesis G/xy admits a plane drawing G.
A partial drawing: Let f be the face of Gv xy containing vxy . The boundary C of f is a cycle, since
G vxy is 2-connected. Let X = NG (x) \ {y} and Y = NG (y) \ {x}. Let G X = G
{vxy v : v Y \ X}
be the drawing G with only those neighbours of vxy left that are in X. G
X may be viewed as a drawing
of G y in which x is represented by vxy . We want to add y back to G X .
Arcs: Fix a direction of the cycle C and enumerate the vertices of X C as x0 , . . . , xk1 . Also, let
P = {xi . . . xi+1 : i Zk } be the set of paths connecting xi and xi+1 along C for all i.
Arc containing Y : Let us show that Y V (P ) for some P P. Assume not. Since G is 3-connected,
x and y each have at least two neighbours in C. By assumption, there exist distinct P 0 , P 00 P and
distinct y 0 , y 00 Y , such that y 0 P 0 , y 00 P 00 , and y 0 , y 00
/ P 0 P 00 . We get a contradiction with
planarity of G as follows:
If Y * X then y 0 can be assumed to be an inner vertex of P 0 , so the endpoints x0 and x00 of
P 0 separate y 0 from y 00 in C. These four vertices together with x and y form a subgraph that is
topologically equivalent to K3,3 (the two stable sets are {x, y 0 , y 00 } and {y, x0 , x00 }).
If Y X then y 0 , y 00 Y X and we consider two cases:
If |Y X| = 2, then y 0 and y 00 must be separated by two neighbours of x and we obtain K3,3
as before.
Otherwise, let y 000 (Y X) \ {y 0 , y 00 }. Then x and y have three common neighbours on C
and these together with x and y form a subgraph that is topologically equivalent to K5 .
Add back vertex y: As Y V (P ) where P = xi . . . xi+1 for some i Zk , the drawing G X can be
extended to a plane drawing of G by putting y in the face fi f of the cycle xxi P xi+1 x.
8
Lemma. If |G| 4 and G is edge-maximal without K5 and K3,3 as topological minors, then G is 3-connected.
Lemma. Let X be a set of 3-connected graphs. Let G be a graph with (G) 2, and let G1 , G2 be proper
induced subgraphs of G such that G = G1 G2 and |G1 G2 | = (G). If G is edge-maximal without a
topological minor in X , then so are G1 and G2 , and G1 G2 = K2 .
asdf: Every vertex v S = V (G1 G2 ) has a neighbour in every component of Gi S for i {1, 2},
otherwise S would separate G, contradicting |S| = (G). By maximality of G, every edge e added to
G lies in a subgraph topologically equivalent to some X X .
9
0.7 Five Colour Theorem
Theorem (Five Colour Theorem). Every planar graph is 5-colourable.
Induction on |V |: Apply induction on |V |. Basis case |V | < 5 is trivial.
Find a vertex of degree 5:
Prove inequality: Prove that E 3V 6 using the following:
Eulers formula: F E + V = 2.
Count edges: 3F 2E, since each face has at least 3 edges.
P
Contradiction: If v V : deg v 6 then 2E = vV deg v 6V . Both inequalities together
give 6V 12 2E 6V , a contradiction.
Degree < 5: By induction hypothesis G v admits a 5-colouring. Since deg v 4, the remaining
colour can be used for v.
Degree = 5:
Pick non-adjacent neighbours: Let a, b be any two non-adjacent neighbours of v (if N (v) = K5
then G is not planar, a contradiction).
Find a colouring with c(a) = c(b): Consider G0 = (Gv +ab)/ab. G0 is planar, so by induction
hypothesis it is 5-colourable. This yields a 5-colouring of G, where a and b get the same colour.
Only 4 colours are used for the neighbours of v, so one colour is left for v.
10
0.8 Brooks Theorem
Theorem (Brooks, 1941). A connected graph G that is neither complete nor an odd cycle has (G) (G).
Induction on |V |: Apply induction on |V |.
Trivial for small : If (G) 2 then in fact (G) = 2 and G is a path of length at least 2 or an
even cycle, so (G) = (G) = 2. From now on assume that (G) 3. In particular, |V | 4. Let
= (G).
-colouring for G v: Let v be any fixed vertex of G and H = G v. To show that (H) , for
each component H 0 of H consider two cases.
Generic case: If H 0 is not complete or an odd cycle, then by induction hypothesis (H 0 )
(H 0 ) .
Complete graph or an odd cycle: If H 0 is complete or an odd cycle, then all its vertices have
maximum degree and at least one is adjacent to v. Hence, (H 0 ) = (H 0 ) + 1 .
Assume the opposite: Assume (G) > (G). This assumption imposes a certain structure on G
leading to a contradiction.
1. Neighbours of v form a rainbow: Since (H) < (G), every -colouring of H uses
all colours on N (v). In particular, deg(v) = . Let N (v) = {v1 , . . . , v } with c(vi ) = i.
2. 2-coloured components: Vertices vi and vj lie in a common component Cij of the subgraph
induced by all vertices of colours i 6= j. Otherwise we could interchange the colours in one of the
components, contradicting property 1.
3. Every component is a path: degG (vk ) so degH (vk ) 1 and the neighbours of vk
have pairwise different colours. Otherwise we could recolour vk contrary to property 1. Thus, the
only neighbour of vi in Cij is on a vi vj path P in Cij , and similarly for vj . If Cij 6= P then
some inner vertex of P has 3 neighbours in H of the same colour. Let u be the first such vertex
on P . Since at most 2 colours are used on its neighbours, we can recolour u, contradicting
property 2. Thus Cij = P .
4. All paths are internally disjoint: If vj 6= u Cij Cjk , then according to property 3 two
neighbours of u are coloured i and two are coloured k. We may recolour u so that vi and vj lie in
different components, contradicting property 2. Hence, all paths Cij are internally vertex-disjoint.
A contradiction: The structure imposed on G is not possible.
Non-adjacent neighbours: If all neighbours of v are adjacent, then G = K+1 , a contradic-
tion. Assume v1 v2
/ E.
First vertex on C12 : Let v1 u be the first edge on the path C12 (u 6= v2 and c(u) = 2). After
interchanging colours 1 and 3 on the path C13 , u is adjacent to a vertex with colour 3, so it also
lies on C23 , a contradiction.
11
0.9 Haj
os Theorem
os, 1961). Let G be a graph and k N. Then (G) k if and only if G has a k-constructible
Theorem (Haj
subgraph.
Definition. The class of k-constructible graphs is defined recursively as follows:
1. Kk is k-constructible.
2. If G is k-constructible and xy
/ E(G) then so is (G + xy)/xy.
3. If G1 and G2 are k-constructible and G1 G2 = {x}, xy1 E(G1 ), and xy2 E(G2 ), then H =
(G1 G2 ) xy1 xy2 + y1 y2 is also k-constructible.
=
Trivial: All k-constructible graphs are at least k-chromatic.
1. (Kk ) = k.
2. If (G + xy)/xy has a colouring with fewer than k colours, then so does G, a contradiction.
3. In any colouring of H vertices y1 and y2 receive different colours, so one of them, say y1 , will be
coloured differently from x. Thus, if H can be coloured with fewer than k colours, then so can
G1 , a contradiction.
=
Assume the opposite: The case k < 3 is trivial, so assume (G) k 3, but G has no k-
constructible subgraph.
Edge-maximal counterexample: If necessary, add some edges to make G edge-maximal with the
property that none of its subgraphs is k-constructible.
Non-adjacency is not an equivalence relation: G cannot be maximal r-partite, otherwise G
admits an r-colouring (colour each stable set with a different colour), hence r (G) k and G
contains a k-constructible subgraph Kk . Thus, there are vertices x, y1 , y2 such that y1 x, xy2
/ E(G)
but y1 y2 E(G). Since G is edge-maximal without a k-constructible subgraph, edge xyi lies in a
k-constructible subgraph Hi G + xyi for each i {1, 2}.
Glue: Let H20 be an isomorphic copy of H2 such that H20 G = (H2 H1 ) + x together with
an isomorphism : H2 H20 : v 7 v 0 that fixes H2 H20 pointwise. Then H1 H20 = {x}, so
H = (H1 H20 ) xy1 xy20 + y1 y20 is k-constructible by step 3.
Identify: To transform H into a subgraph of G, one by one identify each vertex v 0 H20 G with its
copy v 0 . Since vv 0 is never an edge of H, this corresponds to the operation in step 2. Eventually, we
obtain a k-constructible subgraph (H1 H2 ) xy1 xy2 + y1 y2 G.
12
0.10 Vizings Theorem
Theorem (Vizing, 1964). Every graph G satisfies (G) 0 (G) (G) + 1.
First inequality: Clearly, one needs at least colours to colour the edges of G, so 0 (G) . It
remains to show that G admits a ( + 1)-edge-colouring (from now on, simply a colouring).
Induction on |E|: Apply induction on |E|. Basis case E = is trivial.
Every vertex misses a colour: By induction hypothesis G e admits a colouring for every e E.
Edges at a given vertex v use at most deg(v) colours, so some colour [ + 1] is missing at v.
Define /-path: For any 6= there is a unique maximal walk starting at v with edge colours
alternating between and . This walk must be a path, for any internal vertex u with deg(u) 3
would be adjacent to two edges of the same colour.
Assume the opposite: Suppose G has no colouring (that is, 0 (G) > (G) + 1).
End of the /-path: Let xy E and consider any colouring of G xy. If colour is missing
at x and is missing at y, then the /-path from y ends in x. Otherwise interchange and
on this path, so now xy has colour . This gives a colouring of G, a contradiction.
First page: Pick xy0 E. By induction, G0 = G xy0 has a colouring c0 . Let be the
colour missing at x in c0 .
Construct a maximal book: If y0 has colour 0 missing in c0 and x has a neighbour y with
c0 (xy) = 0 , let y1 = y. In general, if i is missing for yi , let yi+1 be such that c0 (xyi+1 ) = i .
Let y0 , y1 , . . . , yk be a maximal such sequence of distinct neighbours of x.
Flip pages: For each graph Gi = G xyi define colouring ci to be identical to c0 , except
ci (xyj ) = c0 (xyj+1 ) if j < i. In each of the graphs Gi vertex x is adjacent to exactly k vertices
from the set {y0 , . . . , yk }. Moreover, the corresponding edges use all k colours from {1 , . . . , k }.
-edge at x: Colour = k is missing at yk in all ci (in particular, in ck ). However, it is not
missing at x in ck , otherwise we could colour xyk with and extend ck . Hence, x has a -edge (in
each ci ). By maximality of k, it must be xyl for some l. In particular, for c0 it is xyl with 0 < l < k
(l 6= 0 since xy0
/ G0 , l 6= k since yk misses ), but for ck this is xyl1 , since c0 (xyl ) = ck (xyl1 ).
A contradiction:
Path P : Let P be the /-path from yk in Gk (with respect to ck ). As is missing at x, P ends
at x with the -edge xyl1 .
Path P 0 : In c0 , . . . , cl1 colour is missing at yl1 . Let P 0 be the /-path from yl1 in Gl1
(with respect to cl1 ). P 0 must start with yl1 P yk and end in x. However, yk has no -edge, a
contradiction.
13
0.11 Tur
ans Theorem
Theorem (Tur an, 1941). Let n and r > 1 be integers. If G is a Kr -free graph with n vertices and the largest
possible number of edges, then G = Tr1 (n), a Turan graph.
Induction on n: Apply induction on n. Basis case n r 1 is trivial, since Kn = Tr1 (n). Thus,
assume n r and let tr1 (n) = kTr1 (n)k.
Complete subgraph of size r 1: Adding any edge to G creates Kr , thus K = Kr1 G.
Upper bound on kGk: By induction hypothesis, kG Kk tr1 (n r + 1). Also, each vertex of
G K has at most r 2 neighbours in K, otherwise adding back K would yield a Kr . Hence,
r1
kGk tr1 (n r + 1) + (n r + 1)(r 2) + = tr1 (n), (1)
2
where the last equality follows by inspection of Tr1 (n). In fact, kGk = tr1 (n), since Tr1 (n) is
Kr -free and G is edge-maximal Kr -free.
Independent sets: Let x1 , x2 , . . . , xr1 be the vertices of K and let Vi = {v V : vxi
/ E}. Since
the inequality (1) is tight, every vertex of G K has exactly r 2 neighbours in K. Thus, vxi /E
if and only if j 6= i : vxj E. Each Vi is independent since Kr * G. Moreover, they partition V .
Hence, G is (r 1)-partite.
Maximality: Tur an graph Tr1 (n) is the unique (r1)-partite graph with n vertices and the maximum
number of edges, since all partition sets differ in size by at most 1. Hence, G = Tr1 (n) by the assumed
extremality of G.
14
