In the mathematical field of graph theory, the windmill graph is an undirected graph constructed for and by joining copies of the complete graph at a shared universal vertex. That is, it is a 1-clique-sum of these complete graphs.
It has vertices and edges, girth 3 (if ), radius 1 and diameter 2. It has vertex connectivity 1 because its central vertex is an articulation point; however, like the complete graphs from which it is formed, it is -edge-connected. It is trivially perfect and a block graph.
By construction, the windmill graph is the friendship graph , the windmill graph is the star graph and the windmill graph is the butterfly graph.
The windmill graph has chromatic number and chromatic index . Its chromatic polynomial can be deduced from the chromatic polynomial of the complete graph and is equal to
The windmill graph is proved not graceful if . In 1979, Bermond has conjectured that is graceful for all . Through an equivalence with perfect difference families, this has been proved for .
Bermond, Kotzig, and Turgeon proved that is not graceful when and or , and when and . The windmill is graceful if and only if or .