{{Short description|Graph of triangles with a shared vertex}} {{infobox graph | name = Friendship graph | image = 120px | image_caption = The friendship graph {{math|''F''{{sub|8}}}}. | vertices = {{math|2''n'' + 1}} | edges = {{math|3''n''}} | automorphisms = | chromatic_number = 3 | girth = 3 | diameter = 2 | radius = 1 | chromatic_index = {{math|2''n''}} |notation = {{mvar|F{{sub|n}}}} | properties = {{plainlist|1= *Unit distance *Planar *Eulerian *Factor-critical *Locally linear }} }} thumb|upright=1.8|The friendship graphs {{math|''F''{{sub|2}}}}, {{math|''F''{{sub|3}}}} and {{math|''F''{{sub|4}}}}.

In the mathematical field of graph theory, the '''friendship graph''' (or '''Dutch windmill graph''' or '''{{mvar|n}}-fan''') {{mvar|F{{sub|n}}}} is a planar, undirected graph with {{math|2''n'' + 1}} vertices and {{math|3''n''}} edges.<ref>{{MathWorld|urlname=DutchWindmillGraph|title=Dutch Windmill Graph|mode=cs2}}</ref>

The friendship graph {{mvar|F{{sub|n}}}} can be constructed by joining {{mvar|n}} copies of the cycle graph {{math|''C''{{sub|3}}}} with a common vertex, which becomes a universal vertex for the graph.<ref>{{citation|last=Gallian|first=Joseph A.|title=A dynamic survey of graph labeling|journal=Electronic Journal of Combinatorics|pages=DS6|date=January 3, 2007|doi=10.37236/27|doi-access=free}}.</ref>

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

==Friendship theorem== The '''friendship theorem''' of {{harvs|first1=Paul|last1=Erdős|author1-link=Paul Erdős|first2=Alfréd|last2=Rényi|author2-link=Alfréd Rényi|first3=Vera T.|last3=Sós|author3-link=Vera T. Sós|year=1966|txt}}<ref>{{citation|first1=Paul|last1=Erdős|author1-link=Paul Erdős|first2=Alfréd|last2=Rényi|author2-link=Alfréd Rényi|first3=Vera T.|last3=Sós|author3-link=Vera T. Sós|url=http://www.renyi.hu/~p_erdos/1966-06.pdf|title=On a problem of graph theory|journal=Studia Sci. Math. Hungar.|volume=1|year=1966|pages=215–235}}.</ref> 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.<ref>{{citation|first1=Václav|last1=Chvátal|author1-link=Václav Chvátal|first2=Anton|last2=Kotzig|author2-link= Anton Kotzig |first3=Ivo G.|last3=Rosenberg|first4=Roy O.|last4=Davies|title=There are <math>\scriptstyle 2^{\aleph_\alpha}</math> friendship graphs of cardinal <math>\scriptstyle\aleph_\alpha</math>|journal=Canadian Mathematical Bulletin|volume=19|issue=4|year=1976|pages=431–433|doi=10.4153/cmb-1976-064-1|doi-access=free}}.</ref>

A combinatorial proof of the friendship theorem was given by Mertzios and Unger.<ref>{{citation|last=Mertzios|first=George|author2=Walter Unger|title=The friendship problem on graphs|journal=Relations, Orders and Graphs: Interaction with Computer Science|date=2008|url=http://www.dur.ac.uk/george.mertzios/papers/Conf/Conf_Windmills.pdf}}</ref> Another proof was given by Craig Huneke.<ref>{{citation|jstor=2695332|title=The Friendship Theorem|first=Craig|last=Huneke|date=1 January 2002|journal=The American Mathematical Monthly|volume=109|issue=2|pages=192–194|doi=10.2307/2695332}}</ref> A formalised proof in Metamath was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.<ref>{{citation|first=Alexander|last=van der Vekens|title=Friendship Theorem (#83 of "100 theorem list")|date=11 October 2018|url=https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ|work=Metamath mailing list}}</ref>

==Labeling and colouring== The friendship graph has chromatic number 3 and chromatic index {{math|2''n''}}. Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph {{math|''C''{{sub|3}}}} and is equal to :<math>(x-2)^n (x-1)^n x</math>.

The friendship graph {{mvar|F{{sub|n}}}} is edge-graceful if and only if {{mvar|n}} is odd. It is graceful if and only if {{math|''n'' ≡ 0 (mod 4)}} or {{math|''n'' ≡ 1 (mod 4)}}.<ref>{{citation | last1 = Bermond | first1 = J.-C. | last2 = Brouwer | first2 = A. E. | author2-link = Andries Brouwer | last3 = Germa | first3 = A. | contribution = Systèmes de triplets et différences associées | mr = 539936 | pages = 35–38 | publisher = CNRS, Paris | series = Colloq. Intern. du CNRS | title = Problèmes Combinatoires et Théorie des Graphes (Univ. Orsay, 1976) | volume = 260 | year = 1978}}.</ref><ref>{{citation | last1 = Bermond | first1 = J.-C. | last2 = Kotzig | first2 = A.|author2-link= Anton Kotzig | last3 = Turgeon | first3 = J. | contribution = On a combinatorial problem of antennas in radioastronomy | mr = 519261 | pages = 135–149 | publisher = North-Holland, Amsterdam-New York | series = Colloq. Math. Soc. János Bolyai | title = Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I | volume = 18 | year = 1978}}.</ref>

Every friendship graph is factor-critical.

==Extremal graph theory== 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 (for <math>n</math> sufficiently large in terms of <math>k</math>) if the number of edges is :<math>\left\lfloor \frac{n^2}{4}\right\rfloor + f(k),</math> 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 (when <math>n\ge 50k^2</math>), in that for any smaller number of edges there exist graphs that do not contain a <math>k</math>-fan.<ref>{{citation | last1 = Erdős | first1 = P. | author1-link = Paul Erdős | last2 = Füredi | first2 = Z. | author2-link = Zoltán Füredi | last3 = Gould | first3 = R. J. | author3-link = Ronald J. Gould | last4 = Gunderson | first4 = D. S. | doi = 10.1006/jctb.1995.1026 | doi-access=free | issue = 1 | journal = Journal of Combinatorial Theory | mr = 1328293 | pages = 89–100 | series = Series B | title = Extremal graphs for intersecting triangles | url = http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_erdos_gould_gunderson_triangles.ps | volume = 64 | year = 1995| citeseerx = 10.1.1.491.974 }}.</ref>

== Generalizations ==

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

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

== References == {{reflist}}

Category:Parametric families of graphs Category:Planar graphs