In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or -fan) is a planar, undirected graph with vertices and edges. The friendship graph can be constructed by joining copies of the cycle graph with a common vertex, which becomes a universal vertex for the graph. By construction, the friendship graph is

isomorphic In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word is ...

to the windmill graph . It is unit distance with

girth Girth may refer to: ;Mathematics * Girth (functional analysis), the length of the shortest centrally symmetric simple closed curve on the unit sphere of a Banach space * Girth (geometry), the perimeter of a parallel projection of a shape * Girth ...

3, diameter 2 and radius 1. The graph is isomorphic to the butterfly graph.

Friendship theorem

The friendship theorem of states that the finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs. Informally, if a group of people has the property that every pair of people has exactly one friend in common, then there must be one person who is a friend to all the others. However, for infinite graphs, there can be many different graphs with the same cardinality that have this property. A combinatorial proof of the friendship theorem was given by Mertzios and Unger. Another proof was given by Craig Huneke. A formalised proof in Metamath was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.

Labeling and colouring

The friendship graph has chromatic number 3 and chromatic index . Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph and is equal to :

(x-2)^n (x-1)^n x

. The friendship graph is edge-graceful if and only if is odd. It is

graceful Gracefulness, or being graceful, is the physical characteristic of displaying "pretty agility", in the form of elegant movement, poise, or balance. The etymological root of ''grace'' is the Latin word ''gratia'' from ''gratus'', meaning pleasing ...

if and only if or . Every friendship graph is factor-critical.

Extremal graph theory

According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a

k

-fan as a subgraph. More specifically, this is true for an

n

-vertex graph if the number of edges is :

\left\lfloor \frac\right\rfloor + f(k),

where

f(k)

k^2-k

k

is odd, and

f(k)

k^2-3k/2

k

is even. These bounds generalize Turán's theorem on the number of edges in a triangle-free graph, and they are the best possible bounds for this problem, in that for any smaller number of edges there exist graphs that do not contain a

k

-fan..

References

{{reflist Parametric families of graphs Planar graphs