Friendship graph

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

${\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 ${\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.[10]