Friendship graph

Friendship graph
The friendship graph F8.
Vertices	2n + 1
Edges	3n
Radius	1
Diameter	2
Girth	3
Chromatic number	3
Chromatic index	2n
Properties	Unit distance Planar Eulerian Factor-critical Locally linear
Notation	Fn
Table of graphs and parameters

In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) F_n is a planar, undirected graph with 2n + 1 vertices and 3n edges.^[1]

The friendship graph F_n can be constructed by joining n copies of the cycle graph C₃ with a common vertex, which becomes a universal vertex for the graph.^[2]

By construction, the friendship graph F_n is isomorphic to the windmill graph Wd(3, n). It is unit distance with girth 3, diameter 2 and radius 1. The graph F₂ is isomorphic to the butterfly graph. Friendship graphs are generalized by the triangular cactus graphs.

The friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966)^[3] 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.^[4]

A combinatorial proof of the friendship theorem was given by Mertzios and Unger.^[5] Another proof was given by Craig Huneke.^[6] A formalised proof in Metamath was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.^[7]

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

( x − 2 ) n ( x − 1 ) n x {\displaystyle (x-2)^{n}(x-1)^{n}x} .

The friendship graph F_n is edge-graceful if and only if n is odd. It is graceful if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).^[8][9]

Every friendship graph is factor-critical.

According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a k {\displaystyle k} -fan as a subgraph. More specifically, this is true for an n {\displaystyle n} -vertex graph (for n {\displaystyle n} sufficiently large in terms of k {\displaystyle k} ) if the number of edges is

⌊ n 2 4 ⌋ + f ( k ) , {\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}

where f ( k ) {\displaystyle f(k)} is k 2 − k {\displaystyle k^{2}-k} if k {\displaystyle k} is odd, and f ( k ) {\displaystyle f(k)} is k 2 − 3 k / 2 {\displaystyle k^{2}-3k/2} if k {\displaystyle 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 ≥ 50 k 2 {\displaystyle n\geq 50k^{2}} ), in that for any smaller number of edges there exist graphs that do not contain a k {\displaystyle k} -fan.^[10]

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 {\displaystyle P_{k}} -graphs, in which any two vertices are connected by a unique path of length k {\displaystyle k} . For k ≥ 3 {\displaystyle k\geq 3} no such graphs are known, and the claim of their non-existence is Kotzig's conjecture.

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