I am studying on Chromatic numbers of graphs and I came across Petersen’s graph.
Petersen’s graph which is an undirected graph with 10 vertices and 15 edges. And it has the chromatic number 3, meaning that its vertices can be colored with three colors — but not with two — such that no edge connects vertices of the same color.
The Question is Let G be obtained from Petersen’s graph by adding no more than three edges. What can the chromatic number of such graph be? List all the possible values.
MY ATTEMPT: From Brooks theorem if G is connected $\chi(G) = \Delta (G) $ unless $G$ is complete or an odd cycle, in which case the $\chi (G) = \Delta (G) = 1 $
So for Case 1: (If I add an additional edge) my $|E| = 16$ edges and $|V|=$ 12 vertices (still an even cycle) i.e $\chi (G) = 3$ still.
For Case 2: (add two edges) 17 edges and 14 vertices (even cycle) $\chi (G) = 3$ still. and likewise for Case 3 $\chi (G) = 3$
Please is my solution correct? Thanks in Advance
$\endgroup$ 5 Reset to default
