Friendship graph
Friendship graph  

The friendship graph F_{8}.  
Vertices  2n + 1 
Edges  3n 
Radius  1 
Diameter  2 
Girth  3 
Chromatic number  3 
Chromatic index  2n 
Properties 

Notation  F_{n} 
Table of graphs and parameters 
In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or nfan) 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_{3} 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_{2} is isomorphic to the butterfly graph. Friendship graphs are generalized by the triangular cactus graphs.
Friendship theorem
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]}
Labeling and colouring
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_{3} and is equal to
 [math]\displaystyle{ (x2)^n (x1)^n x }[/math].
The friendship graph F_{n} is edgegraceful 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 factorcritical.
Extremal graph theory
According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a [math]\displaystyle{ k }[/math]fan as a subgraph. More specifically, this is true for an [math]\displaystyle{ n }[/math]vertex graph if the number of edges is
 [math]\displaystyle{ \left\lfloor \frac{n^2}{4}\right\rfloor + f(k), }[/math]
where [math]\displaystyle{ f(k) }[/math] is [math]\displaystyle{ k^2k }[/math] if [math]\displaystyle{ k }[/math] is odd, and [math]\displaystyle{ f(k) }[/math] is [math]\displaystyle{ k^23k/2 }[/math] if [math]\displaystyle{ k }[/math] is even. These bounds generalize Turán's theorem on the number of edges in a trianglefree 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]\displaystyle{ k }[/math]fan.^{[10]}
References
 ↑ Weisstein, Eric W.. "Dutch Windmill Graph". http://mathworld.wolfram.com/DutchWindmillGraph.html.
 ↑ Gallian, Joseph A. (January 3, 2007), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics: DS6, doi:10.37236/27.
 ↑ Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory", Studia Sci. Math. Hungar. 1: 215–235, http://www.renyi.hu/~p_erdos/196606.pdf.
 ↑ Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are [math]\displaystyle{ \scriptstyle 2^{\aleph_\alpha} }[/math] friendship graphs of cardinal [math]\displaystyle{ \scriptstyle\aleph_\alpha }[/math]", Canadian Mathematical Bulletin 19 (4): 431–433, doi:10.4153/cmb19760641.
 ↑ Mertzios, George; Walter Unger (2008), "The friendship problem on graphs", Relations, Orders and Graphs: Interaction with Computer Science, http://www.dur.ac.uk/george.mertzios/papers/Conf/Conf_Windmills.pdf
 ↑ Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly 109 (2): 192–194, doi:10.2307/2695332
 ↑ van der Vekens, Alexander (11 October 2018), "Friendship Theorem (#83 of "100 theorem list")", Metamath mailing list, https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ
 ↑ Bermond, J.C. (1978), "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976), Colloq. Intern. du CNRS, 260, CNRS, Paris, pp. 35–38.
 ↑ Bermond, J.C. (1978), "On a combinatorial problem of antennas in radioastronomy", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, 18, NorthHolland, AmsterdamNew York, pp. 135–149.
 ↑ "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B 64 (1): 89–100, 1995, doi:10.1006/jctb.1995.1026, http://www.math.uiuc.edu/~zfuredi/PUBS/furedi_erdos_gould_gunderson_triangles.ps.
Original source: https://en.wikipedia.org/wiki/Friendship graph.
Read more 