Question

Prove that \({w_n}\) is chromatically 4-critical whenever n is an odd integer, \(n \geqslant 3\)

Short answer

Above figures show that \({w_n}\) is chromatically 4-critical whenever n is an odd integer

Step-by-step solution

Given information

\({w_n}\): It is obtained by adding a vertex and edges from this vertex to the original vertices in : it represents a wheel of edges of size n, and it is obtained by adding a vertex and edges from this vertex to the original vertices in \({C_n}\)

If the chromatic number of a connected graph G is k, but the chromatic number of the graph produced by deleting this edge from G is k-1, the graph is said to be chromatically k-critical.

Definition

A wheel graph is a graph produced by connecting a single universal vertex to all vertices of a cycle in the mathematical discipline of graph theory. The 1-skeleton of a (n-1)-gonal pyramid can also be defined as a wheel network with n vertices.

Solution

As a wheel graph is obtained from \({C_n}\) by adding vertex and edges from this vertex to the original vertices in\({C_n}\). We need an extra color to the centered vertex. This shows that the chromatic number will also increase by 1 for both odd and even for vertices for \({C_n}\)

Here the graph for \({w_5}\)and \({w_3}\) are chromatically 4-critical, if we delete any edge of \({w_5}\) and \({w_3}\) they will become chromatically 3-critical

The final answer of the question is that

When n is an odd integer, as shown in the diagrams above, it is chromatically 4-critical.