The friendship theorem of Шаблон:Harvs[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]
According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a <math>k</math>-fan as a subgraph. More specifically, this is true for an <math>n</math>-vertex graph if the number of edges is
where <math>f(k)</math> is <math>k^2-k</math> if <math>k</math> is odd, and
<math>f(k)</math> is <math>k^2-3k/2</math> if <math>k</math> 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 <math>k</math>-fan.[10]
