# Friendship graph

> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Friendship_graph
> Markdown URL: https://mediated.wiki/source/Friendship_graph.md
> Source: https://en.wikipedia.org/wiki/Friendship_graph
> Source revision: 1285350519
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)

{{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](/source/Unit_distance_graph)
*[Planar](/source/planar_graph)
*[Eulerian](/source/Eulerian_graph)
*[Factor-critical](/source/Factor-critical_graph)
*[Locally linear](/source/Locally_linear_graph)
}}
}}
thumb|upright=1.8|The friendship graphs {{math|''F''{{sub|2}}}}, {{math|''F''{{sub|3}}}} and {{math|''F''{{sub|4}}}}.

In the [mathematical](/source/mathematics) field of [graph theory](/source/graph_theory), the '''friendship graph''' (or '''Dutch windmill graph''' or '''{{mvar|n}}-fan''') {{mvar|F{{sub|n}}}} is a [planar](/source/planar_graph), [undirected graph](/source/undirected_graph) with {{math|2''n'' + 1}} [vertices](/source/Vertex_(graph_theory)) 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](/source/cycle_graph) {{math|''C''{{sub|3}}}} with a common vertex, which becomes a [universal vertex](/source/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](/source/Graph_isomorphism) to the [windmill graph](/source/windmill_graph) {{math|Wd(3, ''n'')}}. It is [unit distance](/source/Unit_distance_graph) with [girth](/source/Girth_(graph_theory)) 3, diameter 2 and radius 1. The graph {{math|''F''{{sub|2}}}} is isomorphic to the [butterfly graph](/source/butterfly_graph). Friendship graphs are generalized by the [triangular cactus graph](/source/triangular_cactus_graph)s.

==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](/source/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](/source/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](/source/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](/source/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](/source/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](/source/chromatic_number) 3 and [chromatic index](/source/chromatic_index) {{math|2''n''}}. Its [chromatic polynomial](/source/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](/source/Edge-graceful_labeling) if and only if {{mvar|n}} is odd. It is [graceful](/source/Graceful_labeling) 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](/source/Factor-critical_graph).

==Extremal graph theory==
According to [extremal graph theory](/source/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](/source/Tur%C3%A1n's_theorem) on the number of edges in a [triangle-free graph](/source/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](/source/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](/source/Kotzig's_conjecture).

==See also==
*[Central digraph](/source/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

---
Adapted from the Wikipedia article [Friendship graph](https://en.wikipedia.org/wiki/Friendship_graph) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Friendship_graph?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.