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

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.

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) 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.

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

${\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).

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 ${\displaystyle k}$ -fan as a subgraph. More specifically, this is true for an ${\displaystyle n}$ -vertex graph if the number of edges is

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

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