In graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with vertices can also be defined as the 1-skeleton of an pyramid.
Some authors write to denote a wheel graph with vertices (); other authors instead use to denote a wheel graph with vertices (), which is formed by connecting a single vertex to all vertices of a cycle of length . The former notation is used in the rest of this article and in the table on the right.
<nowiki></nowiki> would be the edge set of a wheel graph with vertex set {1, 2, â¦, v} in which the vertex 1 is a universal vertex.
Wheel graphs are planar graphs, and have a unique planar embedding. More specifically, every wheel graph is a Halin graph. They are self-dual: the planar dual of any wheel graph is an isomorphic graph. Every maximal planar graph, other than K<sub>4</sub> = W<sub>4</sub>, contains as a subgraph either W<sub>5</sub> or W<sub>6</sub>.
There is always a Hamiltonian cycle in the wheel graph and there are cycles in W<sub>n</sub> .
For odd values of n, W<sub>n</sub> is a perfect graph with chromatic number 3: the vertices of the cycle can be given two colors, and the center vertex given a third color. For even n, W<sub>n</sub> has chromatic number 4, and (when n âÂÂ¥ 6) is not perfect. W<sub>7</sub> is the only wheel graph that is a unit distance graph in the Euclidean plane.
The chromatic polynomial of the wheel graph W<sub>n</sub> is :
In matroid theory, two particularly important special classes of matroids are the wheel matroids and the whirl matroids, both derived from wheel graphs. The k-wheel matroid is the graphic matroid of a wheel W<sub>k+1</sub>, while the k-whirl matroid is derived from the k-wheel by considering the outer cycle of the wheel, as well as all of its spanning trees, to be independent.
The wheel W<sub>6</sub> supplied a counterexample to a conjecture of Paul Erdà Âs on Ramsey theory: he had conjectured that the complete graph has the smallest Ramsey number among all graphs with the same chromatic number, but Faudree and McKay (1993) showed W<sub>6</sub> has Ramsey number 17 while the complete graph with the same chromatic number, K<sub>4</sub>, has Ramsey number 18. That is, for every 17-vertex graph G, either G or its complement contains W<sub>6</sub> as a subgraph, while neither the 17-vertex Paley graph nor its complement contains a copy of K<sub>4</sub>.