Question

a). What is the chromatic number of the graph obtained from Kn by removing two edges with a common vertex? For credit, justify your answer by clearly explaining why the chromatic number is greater than your answer and why the chromatic number is less than or equal to your answer. (this will prove your answer correct).

b) What is the chromatic number of the graph obtained from Kn by removing two edges without a common vertex? For credit, justify your answer by clearly explaining why the chromatic number is greater than your answer and why the chromatic number is less than or equal to your answer. (this will prove your answer correct).

Answer 1

# A. Let G' be the graph K​​​​​​_n with the two adjacent edges removed. G' is guaranteed to still have a complete subgraph on n − 1 vertices, so the minimum chromatic number would be n − 1.

And, by Brook’s Theorem, since G' is not a complete graph nor an odd cycle, the maximum chromatic number is n− 1 = ∆(G'). So, χ(G' )= n − 1.

#B. By Brooks’ Theorem, we know our chromatic number has decreased, since for a non complete graph G',

χ(G') ≤ ∆(G'), where G' is the graph Kn with two non adjacent edges removed. By removing these two non adjacent edges, however, we don’t reach ∆(G') as the edges being removed results in a largest subgraph of K​​​_{​​​​​​n-2} . This gives that

χ(G') = n − 2