Friendship graph

The friendship graphs Template:Math, Template:Math and Template:Math.

In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or Template:Mvar-fan) Template:Mvar is a planar, undirected graph with Template:Math vertices and Template:Math edges.

The friendship graph Template:Mvar can be constructed by joining Template:Mvar copies of the cycle graph Template:Math with a common vertex, which becomes a universal vertex for the graph.

By construction, the friendship graph Template:Mvar is isomorphic to the windmill graph Template:Math. It is unit distance with girth 3, diameter 2 and radius 1. The graph Template:Math is isomorphic to the butterfly graph. Friendship graphs are generalized by the triangular cactus graphs.

Friendship theorem

The friendship theorem of Template:Harvs 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 Template:Math. Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph Template:Math and is equal to

$(x-2{)}^n(x-1{)}^{n}x$.

The friendship graph Template:Mvar is edge-graceful if and only if Template:Mvar is odd. It is graceful if and only if Template:Math or Template:Math.

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 (for $n$ sufficiently large in terms of $k$) if the number of edges is

$\lfloor \frac{n^2}{4}\rfloor +f(k),$

where $f(k)$ is $k^2-k$ if $k$ is odd, and $f(k)$ is $k^2-3k/2$ if $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 (when $n\ge 50k^2$), in that for any smaller number of edges there exist graphs that do not contain a $k$-fan.

Generalizations

Any two vertices having exactly one neighbor in common is equivalent to any two vertices being connected by exactly one path of length two. This has been generalized to $P_k$-graphs, in which any two vertices are connected by a unique path of length $k$. For $k\ge 3$ no such graphs are known, and the claim of their non-existence is Kotzig's conjecture.

See also

• Central digraph, a directed graph with the property that every two vertices can be connected by a unique two-edge walk