CHAPTER 5: Colourings

Question 1

Started with 4 colour theorem:

Answer 1

Any map can be coloured with
four colours so that adjacent
countries have different colours.
I Posed by Guthrie 1852
I Proved by Appel and Haken
1976

Question 2

DEF:

The chromatic number

Answer 2

The chromatic number χ(G) of a graph G is the least number of
colours needed to colour the vertices so that adjacent vertices have different colours.

Question 3

Theorem (The four colour theorem)

Answer 3

A planar graph G has χ(G) ≤ 4.

Question 4

First examples of chromatic number

The complete graph Kn

Answer 4

The complete graph has χ(Kn) = n

Question 5

First examples of chromatic number

Bipartite graphs

Answer 5

A graph G has χ(G) = 2 if and only if G is bipartite.

Question 6

First examples of chromatic number

The wheel graph Wn

Answer 6

χ(Wn) = (
3 n even
4 n odd

n+1 vertices:
W_3 : χ =4 since its K_4

W_4: χ=3

ANY COLOURING OF W_n is a colouring of C_n as the wheel and central vertec has to be a new colour since it touches all

Question 7

First examples of chromatic number

The empty graph En

Answer 7

The only graphs with χ(G) = 1 are the empty graphs En.

Question 8

How to find χ(G):

in an exam we will find this:
colour with this many colours and explain why we cant do less

Answer 8

Start by finding rough upper and lower bounds.
Upper bound: colour it
Lower bound: often case by case

Finding the χ(G) is NP-hard
So no beautiful answer. But for small graphs not that bad.

Question 9

How to find χ(G):

Upper bound:

Answer 9

If you can colour the vertices of G with k colours so that adjacent vertices don’t share a vertex, then χ(G) ≤ k.

Question 10

How to find χ(G): Lower bound:

Answer 10

Lower bound: often case by case
A few trivial tricks:

I If a vertex is adjacent to everything, as in Wn

I If H is a subgraph of G, then χ(G) ≥ χ(H).

Question 11

χ(C_n):

Answer 11

C2 : χ=2
C_3: χ=3
they all touch each other
C_4:χ=2

C_5: χ=3

If C_n is even then bipartite and 2 colours

3 if n is odd so at least 3

*IN EXAM: last one is the third colour ie try and do with 2 then last with a third

show i cant do with less, explain why.

Question 12

EXAMPLE GRAPH

7 vertex graph

4 cycles 1243 and 4576
edges 23 and 56 and 17

Answer 12

LOWER BOUND:

• can’t do with one colour
• 2? its not bipartite - there are odd cycles
• we see triangles 123 so need at least 3 colours

tried WLOG: without loss of generality
1red
2blue
3 purple

4 cannot be blue or purple so red
5 and 6 can be blue or purple (one of each)
7 can only be blue or purple as touches 1

so here we cannot colour these in 3 colours so need one more colour
χ(G)≥ 4

upper bound:
colour as 4- then χ(G)=4
(last vertex fourth colour)

Question 13

EXAMPLE GRAPH
COMPLICATED SEE SLIDES
10 vertices

Answer 13

*we see odd cycles so not bipartite so more than 2
*3: we see triangles but vertex W_5 around D and one around C
also K_4 subgraph DCIH

*At least 4:Attempt

*Considering cases after:
WLOG

By symmetry we can avoid ‘cases’ ie loss of generality

there is a colouring with 4 colours so χ(Q)=4

Question 14

DEF

∆(G)

Answer 14

∆(G) is the maximum degree of all vertices of G.

Question 15

Lemma about ∆(G)

Answer 15

χ(G) ≤ ∆(G) + 1

Proof.
Colour the vertices one by one in any order.

Colour vertices 1 by 1. SUppose youve coloured vertices V_1 and V_2 using at most ∆(G) + 1

Question 16

χ(G) ≤ ∆(G) + 1

Proof.

I think in exam…

Answer 16

Proof.
Colour the vertices one by one in any order.

Colour vertices 1 by 1. SUppose youve coloured vertices V_1 and V_2 using at most ∆(G) + 1 colours and now we want to colour V_(k+1)
Any colour that V_(k+1) is adjacent to cant be used.

All we know is that the edges out of V_(k+1) is at most ∆(G). Some might not already be coloured, some may have same colours. We have ∆(G) + 1 colours to use. The worst case is that we have used ∆(G) colours so we can colour this anyway by the last unused colour.

Question 17

EXAMPLE: The bound is tight, but for very few graphs:

χ(G) ≤ ∆(G) + 1

Answer 17

**
χ(Kn) = n = ∆(Kn) + 1

For n odd, χ(Cn) = 3 = ∆(Cn) + 1

Question 18

Theorem (Brooks)

Answer 18

If G isn’t a complete graph or an odd cycle, then χ(G) ≤ ∆(G).

Question 19

Suppose you have some things you want to separate into groups, but certain things can’t be in the same group. How many groups do you need?

Answer 19

• Group vacation, several cottages, some people don’t get on
• Storing chemicals, some react dangerously with each other

Make a graph G with:

• • Vertices are the things
• • Edges mean the vertices can’t be in the same group

The groups are the colours.
χ(G) is the lowest feasible number of groups

Question 20

EXAMPLE: X indicated two people cant be in the same groups

AB X
AC X
AF X
AG X
BC X
BD X
BG X
CD X
CE X
DE X
DF X
FE X
EG X
FG X

Answer 20

Circulate graph*
So this forms a graph 
with 7 vertices and drawing these edges graph  coloured WLOG
A=1
B=2
G=3
try to colour in 3 colours as odd cycles indicate not bipartite
C cannot be 1 or 2
c=3
D=1 as connected to C and B
F=2 adjacent to G,A and D
last vertex E is adjacent to all 3 colours so must be 4 colours

SO minimum number of groups are 4

Question 21

Theorem

Chromatic Number for planar graphs

Answer 21

For G a planar graph χ(G) ≤ 6.

Question 22

For G a planar graph χ(G) ≤ 6

PROOF

Answer 22

Step 1: Using Euler’s Theorem
Definition
δ(G) denotes the minimum degree of all vertices in G.

Lemma
For G a simple planar graph δ(G) ≤ 5

Step 2: Induction
We proved χ(G) ≤ ∆(G) + 1 by colouring the vertices of G in any order. The Lemma bounds δ(G) and not ∆(G); need to be a little smarter.

Question 23

Lemma
For G a simple planar graph δ(G) ≤ 5
PROOF

Answer 23

Assume not, then δ(G) bigger than 5

so d(v) ≥ δ(G) ≥ 6

So combine this with V-E handshaking:
2E = sum of d(v) ≥ 6V

• Euler’s Theorem V − E + F = 2
• Face-Edge handshaking

V≤2E/6= EF/3 ≤ 2E/3

Bounds on d(F) come from simple so no loops and multiple edges so d(F) bigger than or equal to 3

*Simple, so d(f ) ≥ 3 for all faces. So 2E ≥ 3F

Question 24

Proof of the Six Colour Theorem

Answer 24

Assume G is planar. We can assume that G is simple.

Induct on n the number of vertices

Base case: n ≤ 6
At most six vertices, so can give each vertex a different colour.

Inductive Step
Assume that G has n vertices, and every planar simple graph with less than n vertices can be coloured with six colours.

I By the Lemma, G has a vertex v with d(v) ≤ 5

I The graph G \ v has n − 1 vertices, so can be six coloured

I Now colour v

Question 25

DEF Chromatic index

χ’(G)

Answer 25

The chromatic index χ’(G) denotes the minimum number of colours needed to colour the edges of G so that any two edges that share a vertex have different colours.

Question 26

Suppose six teams A − F are in a soccer league, and each team
will play three games:
A
X B
X X C
X D
X X E
X X X F
If each team plays one game a week, can the tournament be run in three weeks? How about if we want AB and DE to play on different weeks?

Answer 26

Make it a graph: Colour minimum colours EDGES

In the application: the colours were the weeks?

Every team playing at least 3, so we look to see if 3 is minimum

6 teams and edges are games they must play

triangle ABC DEF
4 cycles ABED
CBEF

label numbers
for each vertex they dont see the same number twice coming out of them: teams play one game per week at max

WLOG
AB=2
AC=3
CB=1

then we must have
AD=1
CF=2
BE =3
ED=2 
EF=1
DF=3

Question 27

in exam

Answer 27

We will definitely do proofs similar to 6 colour, ie eulers theorem, handshaking, simple proofs

colouring vertices, chromatic number prove and colour by cases that cant be done with less

we will also look at chromatic index and….

lower bound try- try to make no choices and use every case! SHOW if choice made- try with more colours again SHOW then done

• quote Vizings theorem
• define chromatic index of this graph
• justify

Question 28

χ’(K4) =

Answer 28

χ’(K4) = 3

K_4 has vertices of degree 3 so χ’(K4) is at least 3. Trying to colour works:

Question 29

Lemma on and degrees

χ’ (G)

Answer 29

Lemma

χ’ (G) ≥ ∆(G)

Question 30

χ’(K5) =

Answer 30

χ’(K5) = 5

We know its at least 4 as degrees are all 4: attempting this leads us to need 5

symmetry was used

so we need to use every case unless cant use symmetry*****]

another proof: that bigger than or equal to 5
K5 has 10 edges. In any graph, if we have k edges of one colour all 2K vertices they touch have to be different. In K5 at most 5 / 2 = 2 edges of any one colour. If I have 4 colours can do at most 4 x 2 = 8 edges. Not enough

Question 31

Theorem (Vizing)

χ’(

ON EXAM

Answer 31

For a simple graph χ’(G) = ∆ or ∆ + 1

SO TRY ∆ then we know ∆ +1 for EDGES coloured

**in EXAM??

TRY delta if not
we know delta +1

Question 32

One method to find χ’(G) with proof:

Answer 32

We know χ’(G) ≥ ∆(G). Try to colour it with ∆(G)

• • If we can, we have shown χ’(G) = ∆
• • If we can’t, prove it: so we know χ’(G) ≥ ∆ + 1
• • Find a colouring with ∆ + 1 colours

Question 33

Example

Kn for n odd

Answer 33

Kn for n odd Suppose n = 2k + 1 is odd.

• Then ∆(Kn) = n − 1 = 2k
• Kn has k(2k + 1) edges.
• We can have at most k edges of any given colour

*So using 2k colours, can only colour 2k
2 < k(2k + 1) edges

Question 34

EXAMPLE: NOTE

Answer 34

In lemma we need to use G is simple or we could just add loops or null edges eg wheel

Question 35

Example: K_5

Kn for n odd

????

Answer 35

we have 5 vertices, 10 edges we have at least two different colours.
K vertices of one colour then all 2k edges that touch must have different colour to each other

10 edges so need 5 colours

Question 36

Example
Kn for n odd

…

Answer 36

If n is odd we know χ’(G) ≥n
∆((K_n) = n-1

By counting arguement, K_n has nC2 = n(n-1)/2 edges. If n odd , n=2k+1.

#edges (2k+!)(2k)/2 = k(2k+1)
How many edges can i have of one colour?
Half the # vertices  2k+1  /2 = k + 0.5 ***

So if we have n-1 =2k colours we can only colour (#colours) #edges of every colour 2k(k) less than 2k^2 +k
=total # edges

Question 37

Chromatic Polynomial

DEF

Answer 37

counting different colours that are possible

*not unique to graphs

Let G be a SIMPLE graph, and let k ≥ 1 be an integer. The
chromatic polynomial P_G (k) is the number of different ways to
colour the vertices of G with k colours, so that adjacent vertices have different colours.

Question 38

PG (k) = 0

Answer 38

PG (k) = 0 ⇐⇒ 0 ≤ k < χ(G)

Question 39

Chromatic Polynomial

FINDING

Answer 39

In easy examples, can colour vertex by vertex:

can be written χ_G(k)

• P_{E_n}(k) =k^n
• P{Kn}(k) = k(k − 1)(k − 2)· · ·(k − n + 1)
• If T is a tree with n vertices, then PT (k) = k(k − 1)n

Question 40

Chromatic Polynomial

of E_n

Answer 40

empty graph on n vertices
For 3 colours we have 3 choices for every vertex as none are adjacent
P_{E_5}(3)=3^5
P_{E_n}(k)=k^n

for k colours

Question 41

Chromatic Polynomial

of K_n

Answer 41

For complete graph every single vertex is adjacent to every other.
For k colours:
I choose K colours for the first
for second vertex v_2 cant use the same colour as v_1 so k-1
* V_3 cant be the same colour as 1 or 2 so k-2 choices

For K_4 we need at least 4 colours

• P{Kn}(k) = k(k − 1)(k − 2)· · ·(k − n + 1)

Question 42

EXAMPLES
chromatic # of tree
          x
x-x-x<
         x

ABCD
st E is connected to C

Answer 42

order might affect
Starting in middle at vertex B we have K colours
A has k-1 as cant be the same as B
C has k-1 as cant be the same as A
D has k-1 as cant be the same  as c
E has k-1 for the same reason

PG (k) = K(K-1)^{}?

Question 43

CHROMATIC polynomial of a TREE

Answer 43

For any tree:
ALL TREES ON n VERTICES have the SAME CHROMATIC POLYNOMIAL

only adjacent to one thing if it was adjacent to two things there would be a loop and we wouldn’t have a tree because it’s only adjacent to one thing . We can only choose from k - 1 colours for every other vertex after our first.

For tree T on n vertices
P_T (k) = k(k-1)^{n-1}????

not?
* If T is a tree with n vertices, then PT (k) = k(k − 1)n????

Question 44

EXAMPLE

CHROMATIC polynomial of

A-B-D-C-A and edge B-C

Answer 44

• choose colour A out of K
• B has k-1 choices
• If we choose D next we see K-1 ways as its adjacent to B

*But then colouring C gives a problem:
We might have A and D the same colour (they werent adjacent to each other but are to C)
If theyre the same then C is only touching two colours: k-2 choices

If theyre different then C is touching 3 so k-3

*If we start from a different way we can find in another order by looking at the triangle first otherwise we have to do case by case analysis

P_G (k) = k(k-1)(k-2)^2

why not?
P_G (k) = k(k-1)(k-2)(k-3)?
WHICH??

Question 45

EXAMPLE
Bowtie graph
CHROMATIC polynomial of
A-C-D-E-C-B-A

Answer 45

A-k
B-k-1
C-k-2
D-k-1
E-K-2

P_G (k) = k(k-1)^2(k-2)^2

Question 46

CHROMATIC polynomial of

U-V-W
V-X-Y-W
W-X
Y-Z

Answer 46

Z-K
Y-k-1
X-k-1
W- k-3 (adjacent to 2 already coloured that are different colours)
V-k-2
u-k-2`

P_G (k) = k(k-1)^2(k-2)^2(k-3)

Question 47

CHROMATIC polynomial

PATTERNS

Answer 47

deg(K_n)= #vertices

colour vertices with i choices
to the powers total n

Question 48

CASE BY CASE EXAMPLE

CHROMATIC polynomial
C_4

Answer 48

the chromatic number is hard as cases are involved:
k ways to colour vertex 1
I k − 1 ways to colour vertex 2
I k − 1 ways to colour vertex 3

Don’t know if v1 and v3 have same colour
__________

CASE 1: 1 and 3 same colour

1 has k choices 2 has k-1 choices
3 is the same as 1 so no choice
4 has k-1 choices as adjacent to 1 and 3
k(k-1)^2

(powers =3 not 4)

CASE 2: 1 and 3 different colours
1 has k choices
3 is only adjacent to 2 and is not the same as 1 in our case so has k-1 choices (forced different colour)
2 we have forced 1 and 3 to be different so k-2 choices
4 we know 1 and 3 different colours so k-2

k(k-1)(k-2)^2

Factorising:
k(k-1)(k-1)
k(k-1)(k^2-4k+4)
ADDING THESE

P_C(k)= k(k-1)[k^2-3k+3]

Question 49

same colour in chromatic poolynomial

Answer 49

IF THEYRE THE SAME COLOUR WE CAN MERGE VETICES

(2)-(1,3)-(4)

(1,3) has k

(2) has k-1
(4) has k-1

(2)=(1,3)=(4)

Question 50

CASE BY CASE

CHROMATIC polynomial

Answer 50

Case 1: v1 and v2 are the same colour

If they’re the same colour, then we can make them same vertex…

Case 2: V2 and v3 are different colours

If there’s an edge between two vertices, then they need to be different colours.

Question 51

Different colour case chromatic polynomial

Answer 51

BY SAYING theyre the different colours we have added/forced an edge 1-3 when there wasnt one

1-2-3-4 and added 1-3 by saying 1 and 3 different colours

Question 52

WHEN DO WE CONSIDER CASES chromatic polynomial

Answer 52

for any graphs with vertices (pairs) which aren’t adjacent, we consider the cases of whether or not they have different colour

Question 53

CHROMATIC polynomial of C_5

Answer 53

We consider cases for non adjacent vertices:
1=k
5 and 2 could be the same

CASE 1: 5 and 2 same
1=k
5=k-1
2=1 choice
3=k-1
4=k-2 as adjacent to 5 and 3

k(k-1)^2(k-2)

CASE 2: 5 and 2 different**
1=k
2=k-1
5=k-2
3=now 4 and 2 could be the same so we have another case
**4 and 2 the same
4=1
3=k-1 as only adj to one colour

k(k-1)^2(k-2)

CASE 3:5 and 2 different and 4 different to 2 (4 adj to 5 so will be diff)
1=k
2=k-1
5=k-2
4=k-2 as adjacent to 5 and is not the same as 2
3=k-2 as adjacent to 2 different colours

k(k-1)(k-2)^3

so polynomial is
2k(k-1)^2(k-2) + k(k-1)(k-2)^3
=k(k-1)(k-2)[2(k-1) +(k-2)^2]
=k(k-1)(k-2)[2k-2+k^2+4-4k]
=k(k-1)(k-2)[k^2-2k+2]

Question 54

CHROMATIC polynomial of C_5

notes

Answer 54

in the lecture he consider different cases to example:

CASE 1 1, 3 ,4 diff colours
k(k-1)(k-2)^3
= my case 3 symmetry

CASE 2 1 and 3 same colour
= my case ??
CASE 3 1 and 4 same colour

Question 55

Example

G_{+XY}

Answer 55

adding Vertex XY to original

P_{G_{+XY}}(k) = # colourings in P_G(k) where X and Y have different colours

Question 56

G_{X=Y}

Answer 56

creating new Vertex by merging X and Y

multiple edge merged (X=Y)
P_{G_{+XY}} = # colouringd og G where X and Y have same colour

Question 57

LEMMA
Suppose that G is a graph, and x and y are two vertices that
aren’t adjacent. Define:

CHROMATIC POLYNOMIAL

Answer 57

I G+xy to be the graph with the edge xy added
I Gx=y to be the graph with x and y identified

Then:
PG (k) = PG+xy(k) + PGx=y(k)

Question 58

LEMMA
Suppose that G is a graph, and x and y are two vertices that
aren’t adjacent. Define:

PG (k) = PG+xy(k) + PGx=y(k)

Answer 58

Proof.
Consider a colouring of G; in some of them x and y will have
different colourings, and in others x and y will have the same colour. The colourings in the first case are exactly the colourings of G+xy , the colourings in the second are the colourings of Gx=y.

Question 59

The chromatic polynomial of C5

notes???

during the 3 which become two cases

joining vertices 1 and 4

adding edge between 1 and 4

Answer 59

The chromatic polynomial of C5

Three cases, but two are the same:
I Case 1: 1,3 and 4 all have different
colours
I Case 2: 1 and 3 have the same colour
I Case 3: 1 and 4 have the same colour
By symmetry, Cases 2 and 3 are the same.
I Case 1 gives: k(k − 1)(k − 2)^3
I Cases 2 and 3 each give: k(k − 1)^2(k − 2)

PC5(k) = k(k − 1)(k − 2)3 + 2k(k − 1)2(k − 2)
= k(k − 1)(k − 2)[k^2 − 4k + 4 + 2k − 2]

= k(k − 1)(k − 2)(k^2 − 2k + 2)

Question 60

Chromatic number

Chromatic index

Chromatic polynomial

Answer 60

Chromatic number χ(G): colour vertices with fewest colours

I Chromatic index χ’(G): colour edges with fewest colours

I Chromatic polynomial P_G (k): number of ways to colour
vertices with k colours

• Some graphs: colour vertex by vertex: if just triangles then do vertex by vertex
• in general case by case

Question 61

Chromatic polynomial of C4 and a Lemma

Answer 61

Let x and y be two non-adjacent vertices in G. Then
PG (k) = PG+xy
(k) + PGx=y (k)

so CASE 1 and 3 different graphs

k(k − 1)(k − 2)^2

1-2-3-4-1 and 1-3
CASE 1 and 3 same colour
2=(1,3)=4
k(k − 1)^2

PC4
(k) = k(k − 1)(k − 2)2 + k(k − 1)2 = k(k − 1)(k^2 − 3k + 3)

Question 62

Lemma (Deletion-Contraction)

Answer 62

Let H be a graph, and let e be an edge in H. Then
PH(k) = P_{H\e}(k) − P{H/e}(k)

The edge e is between xy

H = G + xy,
H \ e = G,
H/e = Gx=y

** P_H(k)
= deleted edge P - contracted edge P

from PG (k) = PG+xy(k) + PGx=y (k)

PG (k) - PGx=y (k) =
PG+xy(k)

• we use this to get a smaller graph
• one will always have a smallr degree

Question 63

Chromatic polynomial is a polynomial

Answer 63

Theorem

Let G be a simple graph. Then PG (k) is a polynomial in k.
Moreover, if G has n vertices and m edges, then
PG (k) = k^n − mk^{n−1} + lower order terms

Question 64

Chromatic polynomial is a polynomial

PROOF

Answer 64

Proof idea:
Induct on the number of edges using deletion-contraction.
Base case: m = 0

If G has no edges and n vertices, then G = En empty graph.
PEn = k^n is a polynomial of the right form.

Inductive step
Assume that G has m > 0 edges and n vertices, and that for any
graph H with l < m edges and p vertices, we have
PH(k) = k^p − lk^{p−1} + · · · .

Let e ∈ G be any edge:

• G \ e has n vertices and m − 1 edges
• G/e has n − 1 vertices and at most m − 1 edges

So by the inductive hypothesis, theorem holds for G \ e and G/e
So applying Deletion-Contraction:

PG (k) = PG\e
(k) − PG/e(k)
= (k^n − (m − 1)k^{n−1} + · · ·) −
(k^{n−1} − · · · )
= k^n − mk^{n−1} + · · ·

Which is what we needed to show

Question 65

Compute c_4 chromatic polynomial using deletion contraction

Answer 65

P_(c_4)(k)= P_(C4\e) (k) - P_(C4/e)(k)

ie deleted - contracted

P_(C4\e) (k) = is a tree so chromatic polynomial k(k-1)^3

P_(C4/e)(k) =contracted to triangle so k(k-1)(k-2)

SO deletion contraction gives
P_(c_4)(k)= k(k-1)[k^2 -3k+3]

Question 66

Deletion-Contraction as an algorithm

Answer 66

I Can always find PG (x) by iterating deletion-contraction

I In practise, often faster to add edges

(we are taking them away in deletion contraction and easier to calculate chromatic polynomial)

how can we make into tree or how can we make into triangle
= determines which way we use to find

Question 67

Information in PG (k)

ON EXAM

Answer 67

chromatic polynomial: is not unique to graphs but we CAN find out some info about the graph from it

(same polynomial for all trees for example, K_n, E_n)

I Number of vertices is the degree

I Number of edges is negative the coefficient of next highest term
neg coeff of 2nd highest term

I χ(G) is the lowest k with PG (k) not equal to 0.

____
EXAM QUESTION:
SUppose you know the graph has this chromatic polynomial. How many vertices? How many edges?

If i plug in K it will tell me how many ways can i colour the vertices in K colours.
The chromatic number is the lowest amount of colours so lowest term not less than or equal to 0

*C_4 i cant plug 0 or 1 but i can plug in 2
might have to solve one in exam

*C_5 chromatic number is 3 so we know that the polynomial will have (k-1) and (k-2) as factors and a quadratic part left (degree must be 5, 5 edges so -5 is coeff of second highest k^4 term has coeff -5)

= k(k − 1)(k − 2)(k^2 − 2k + 2)

Question 68

Use induction to calculate PG (k) for a family of graphs. We’ll
do Cn

Answer 68

Use induction to calculate PG (k) for a family of graphs. We’ll
do Cn

Gluing formulas for graphs that are nearly disconnected

Question 69

deletion contraction on graph

a-b-c-d-a and edge e between a and c

Answer 69

G/e is graph where edge e contracted

b) = (a,c)=(d
(b) -(a,c)-(d)
* labels just to write this in notes, unlabelled examples

Question 70

PROOF THAT SHOWS UP ON THE EXAM SOMEHOW??

Answer 70

Theorem
Let G be a simple graph. Then PG (k) is a polynomial in k.
Moreover, if G has n vertices and m edges, then
P_G (k) = k^n − mk^{n−1} + lower order terms

Proof idea:
Induct on the number of edges using deletion-contraction.

Base case: m = 0
If G has no edges and n vertices, then G = En empty graph. PEn = k^ n
is a polynomial of the right form

Inductive step
Assume that G has m > 0 edges and n vertices, and that for any graph H with l < m edges and p vertices, we have
PH(k) = k^p − lk^{p−1} + · · · .

Let e ∈ G be any edge:

• G \ e has n vertices and m − 1 edges
• G/e has n − 1 vertices and at most m − 1 edges

So by the inductive hypothesis, theorem holds for G \ e and G/e
So applying Deletion-Contraction:

PG (k) = PG\e
(k) − PG/e(k)
= (k^n − (m − 1)k^{n−1} + · · ·) −
(k^{n−1} − · · · )
= k^n − mk^{n−1} + · · ·

what we needed.

Question 71

Deletion contration for graph
abcdga and bfc

METHOD 1

Answer 71

so P_G(k)

edge e is ga

P_G
=P_G\e(k) - P_(G/e)(k)

PG\e(k) =
(k-1)P_C(k)

4 cycle and one edge going off

P_(G/e)(k)=
k(k-1)(k-2)^2
4 cycle and an edge between 2 non adjacent
looks like ice-cream cone

(edge between them)

(k-1) - k(k-1)(k-2)^2
=k(k-1)(k^3-5k^2+10k-7)

5 vertices = 5 degrees
can be cplpured in 2 colours- bipartite

Question 72

chromatic poly of bipartite

Answer 72

is bipartite so doesnt have a k-2 term!

Question 73

potentially in exam:

Answer 73

state deletion contraction, prove deletion contraction,
use deletion contraction to prove its a polynomial

YOU WILL HAVE TO PROVE EULERS THEOREM!!

Question 74

Calculating the chromatic polynomial of Cn

Answer 74

Let e be any edge of C_n. Then:

C_n /e ∼= C_{n-1}

C_n\e = P_n a tree so P_{P_n}(k)=k(k-1)^{n-1}

(*if we delete edge e its k(k-1)^{n-1}
*if we contract edge e then it becomes C_{n-1}, looks like we can find C_n by ….C_0}

SO we should be able to find P_{C_n }(k) using induction:

P4(k) =k^4 − 4k^3 + 6k^2 − 3k
P5(k) =k^5 − 5k^4 + 10k^3 − 10k^2 + 4k

P6(k) =k^6 − 6k^5 + 15k^4 − 20k^3 + 15k^3 − 5k

P7(k) =k^7 − 7k^6 + 21k^5 − 35k^4 + 35k^3 − 21k^2 + 6k

Looks like:
Pn(k) = (k − 1)^n + (−1)^n(k − 1)

(pascals triangle)

Question 75

COMPUTING FAMILY OF GRAPHS CHROMATIC POLYNOMIAL

Answer 75

probably in exam?

using induction contraction (similar to proving its a polynomial)

• there was an old exam where they used a different way to find chromatic polynomial for C_n but for the Cn-cycle this way
• ON THE EXAM: There are questions where you use induction to find the chromatic formula; deletion contraction allows for this
• we know for trees, we know for complete, we know for empty in this way
• on exam one that could show up is glue vertex / glue edge

Question 76

Prove that:
Looks like:
P_{C_n}(k) = (k − 1)^n + (−1)^n(k − 1)
(we will have to so something similar in exam)

Answer 76

USE INDUCTION:
BASE CASE: n=3 (the first time C_n is a simple graph)

P_{C_3}(k) = k(k-1)(k-2)= k^3 -3k^2 +2k

as required

INDUCTIVE STEP: Assume that we know P_{C_{n-1}}(k) = (k-1)^{n-1} +(-1)^{n-1}(k-1)

want to find P_{C_n}(k), if e is any edge then C_n\e = P_n

o-o-o-o..-o-o n vertices
SO
P_{C_n\e}(k) = k(k-1)^{n-1}

And by C_n\e =C_{n-1}

inductive hypothesis implies
P_{C_n/e}= (k-1)^{n-1} + (-1)^{n-1}(k-1)

SO by deletion contraction:
P_{C_n}(k)
=k(k-1)^{n-1} - [ (k-1)^{n-1} + (-1)^{n-1}(k-1)]
=(k-1)^{n-1}[k-1] +(-1)^n(k-1)
WHICH IS WHAT WE NEEDED TO SHOW

Question 77

EXAMPLE

G is 2 disjoint triangles

Answer 77

Dont affect each other so we can have combinations between them also:

P_G(k) = P_(C_3)(k)* P_(C_3)(k)

1=k
2=k-1
3=k-2

so k^2(k-1)^2(k-2)^2

Question 78

Lemma

DISJOINT UNIONS CHROMATIC POLY

Answer 78

If G is the disjoint union of G1 and G2, then
P_G (k) = PG_1(k)PG_2(k)

Proof.
Colouring G is exactly the same as colouring G1 and G2
independently.

Question 79

NOTES
Lemma
DISJOINT UNIONS CHROMATIC POLY

Answer 79

SINCE P_G(0) =0 by definition . P_G(k) is always divisible by K. (its always a factor) By our lemma on disjoint unions if G has connected components then P_G(k) is divisible by K^C.

2 components then divisible by k^2

Question 80

Gluing formulas: when G isn’t quite a disjoint union

Answer 80

Idea: Colour G1, then extend to a colouring of G2.

Question 81

LEMMA

gluing two graphs along a vertex

Answer 81

Lemma
If G is made by gluing G1 and G2 along a vertex v, then:
PG (k) = (1/k)PG_1(k)PG_2(k)

Question 82

LEMMA WE WONT USE

Answer 82

G has C connected components

IFF K^C is the highest power of K dividing P_G(K)

Question 83

LEMMA 
gluing two graphs along a vertex
Lemma
If G is made by gluing G1 and G2 along a vertex v, then:
PG (k) = (1/k)PG_1(k)PG_2(k)

PROOF

Answer 83

Proof.
First colour G1 in any of the PG1 (k) ways. Now, vertex v of G2 is already coloured, but none of the rest. Since the colours are interchangable, exactly 1/k of the ways of colouring G2 will have
the right colour at v

consider possible colour combinations of the two triangles, we can only glue them together if the colours are the same for the glued vertex

Question 84

Lemma

If G is made by gluing G1 and G2 along an edge e, then

Answer 84

Lemma
If G is made by gluing G1 and G2 along an edge e, then
PG (k) = 1/{k(k − 1)} P_{G_1}(k)P_{G_2}(k)

(probability/proportion that glue together)

Question 85

EXAMPLE 2 triangles glued at a vertex:

BOWTIE

Answer 85

P_G(k)= k(k-1)^2(k-2)^2
= [P_C_3(k)^2]/k

consider possible colour combinations of the two triangles, we can only glue them together if the colours are the same for the glued vertex

Question 86

EXAMPLE 2 triangles glued at an edge

a-b-c-d-a and b-d

Answer 86

P_G(k) = k(k-1)(k-2)^2

=[P_(c_3)(k)^2]/[k(k-1)]

Question 87

graph
abcda and bfd

METHOD 2

Answer 87

we saw that we could find the polynomial by using deletion contraction twice.

it is easier to add an extra Edge use case by case looking at non-adjacent vertices:

CASE 1: v and w have same colour: k choices and k-1 choices for each of other 3 k(k-1)^3

CASE 2: v and w have different colours: K choices for v, k-1 choices for w and k-2 choices for others k(k-1)(k-2)^3

P_G(k) = k(k-1)^3 + k(k-1)(k-2)^3

=k(k-1)[k^3-5k^2 +10k-7]

Question 88

Gluing:

in exam

Answer 88

only edge or vertex would come up

cant do complete graphs but gluing more complicated wont come up

*given a graph to glue

*could ask to prove or state or use specific method gluing formula probably not but more likely deletion contraction
*Here is a graph what is the chromatic polynomial:
we could use deletion contraction loads of times so in exam only a few times used

case by case or deletion contraction (in only a few cases)

*could do by deletion contraction but look if case by case?

Question 89

*POINTING OUT:
graph
**in exam?

Answer 89

graph abcd and edge e connected to every vertex

obervation
:

K choices for the central Vertex so can never use that colour again

so P_g(k) =kP_(C_4)(k-1)
works whenever you have one Vertex to everything