Wheel graph

Wheel graph
Several examples of wheel graphs
Vertices	n
Edges	2(n − 1)
Diameter	2 if n>4 1 if n=4
Girth	3
Chromatic number	3 if n is odd 4 if n is even
Spectrum	${\displaystyle \{2\cos(2k\pi /(n-1))^{1};}$ ${\displaystyle k=1,\ldots ,n-2\}}$${\displaystyle \cup \{1\pm {\sqrt {n}}\}}$
Properties	Hamiltonian Self-dual Planar
Notation	Wn

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n-1)-gonal pyramid. Some authors write W_n to denote a wheel graph with n vertices (n ≥ 4); other authors instead use W_n to denote a wheel graph with n+1 vertices (n ≥ 3), which is formed by connecting a single vertex to all vertices of a cycle of length n. In the rest of this article we use the former notation.

Given a vertex set of {1,2,3,…,v}, the edge set of the wheel graph can be represented in set-builder notation by {{1,2},{1,3},…,{1,v},{2,3},{3,4},…,{v-1,v},{v,2}}.

Wheel graphs are planar graphs, and as such 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₄ = W₄, contains as a subgraph either W₅ or W₆.

There is always a Hamiltonian cycle in the wheel graph and there are ${\displaystyle n^{2}-3n+3}$ cycles in W_n (sequence in the OEIS).