Friendship graph

<h2 id="friendship-theorem">Friendship theorem</h2>
The friendship theorem of <a href="/facts/Paul_Erd%C5%91s/63LoUTe1">Paul Erdős</a>, <a href="/facts/Alfr%C3%A9d_R%C3%A9nyi/q7Dx7fgB">Alfréd Rényi</a>, and <a href="/facts/Vera_T._S%C3%B3s/1w4tA6LD">Vera T. Sós</a> (1966)<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> 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.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a>
A combinatorial proof of the friendship theorem was given by Mertzios and Unger.<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> Another proof was given by Craig Huneke.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> A formalised proof in <a href="/facts/Metamath/CcXV4bnF">Metamath</a> was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a>

<h2 id="labeling-and-colouring">Labeling and colouring</h2>
The friendship graph has <a href="/facts/Chromatic_number/J6HoBfP0">chromatic number</a> 3 and <a href="/facts/Chromatic_index/AcdpUxCv">chromatic index</a> 2n. Its <a href="/facts/Chromatic_polynomial/dvr4Hyz9">chromatic polynomial</a> can be deduced from the chromatic polynomial of the cycle graph C3 and is equal to

(
 x
 −
 2
 
 )
 
 n
 
 
 (
 x
 −
 1
 
 )
 
 n
 
 
 x
 
 
 {\displaystyle (x-2)^{n}(x-1)^{n}x}
 
.
The friendship graph Fn is <a href="/facts/Edge-graceful_labeling/kU4aaKyw">edge-graceful</a> if and only if n is odd. It is <a href="/facts/Graceful_labeling/Do7bxMnc">graceful</a> if and only if n ≡ 0 (mod 4) or n ≡ 1 (mod 4).<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a><a class="footnote-ref" id="fnref:9" href="#fn:9">9</a>
Every friendship graph is <a href="/facts/Factor-critical_graph/CT2eT98n">factor-critical</a>.

<h2 id="extremal-graph-theory">Extremal graph theory</h2>
According to <a href="/facts/Extremal_graph_theory/mdkBX6yN">extremal graph theory</a>, every graph with sufficiently many edges (relative to its number of vertices) must contain a 
 
 
 
 k
 
 
 {\displaystyle k}
 
-fan as a subgraph. More specifically, this is true for an 
 
 
 
 n
 
 
 {\displaystyle n}
 
-vertex graph (for 
 
 
 
 n
 
 
 {\displaystyle n}
 
 sufficiently large in terms of 
 
 
 
 k
 
 
 {\displaystyle k}
 
) if the number of edges is

⌊
          
            
              
                n
                
                  2
                
              
              4
            
          
          ⌋
        
        +
        f
        (
        k
        )
        ,
      
    
    {\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}

where 
 
 
 
 f
 (
 k
 )
 
 
 {\displaystyle f(k)}
 
 is 
 
 
 
 
 k
 
 2
 
 
 −
 k
 
 
 {\displaystyle k^{2}-k}
 
 if 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is odd, and

f
 (
 k
 )
 
 
 {\displaystyle f(k)}
 
 is 
 
 
 
 
 k
 
 2
 
 
 −
 3
 k
 
 /
 
 2
 
 
 {\displaystyle k^{2}-3k/2}
 
 if 
 
 
 
 k
 
 
 {\displaystyle k}
 
 is even. These bounds generalize <a href="/facts/Tur%C3%A1n%27s_theorem/opMCT84y">Turán's theorem</a> on the number of edges in a <a href="/facts/Triangle-free_graph/8D3LJ44h">triangle-free graph</a>, and they are the best possible bounds for this problem (when 
 
 
 
 n
 ≥
 50
 
 k
 
 2
 
 
 
 
 {\displaystyle n\geq 50k^{2}}
 
), in that for any smaller number of edges there exist graphs that do not contain a 
 
 
 
 k
 
 
 {\displaystyle k}
 
-fan.<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a>

<h2 id="generalizations">Generalizations</h2>
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 
 
 
 
 
 P
 
 k
 
 
 
 
 {\displaystyle P_{k}}
 
-graphs, in which any two vertices are connected by a unique path of length 
 
 
 
 k
 
 
 {\displaystyle k}
 
. For 
 
 
 
 k
 ≥
 3
 
 
 {\displaystyle k\geq 3}
 
 no such graphs are known, and the claim of their non-existence is <a href="/facts/Kotzig%27s_conjecture/GcoVa8Ik">Kotzig's conjecture</a>.

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Central_digraph/1B59RxQw">Central digraph</a>, a directed graph with the property that every two vertices can be connected by a unique two-edge walk</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Weisstein, Eric W., "Dutch Windmill Graph", MathWorld <a href="/wiki/Eric_W._Weisstein" target="_blank">/wiki/Eric_W._Weisstein</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">Gallian, Joseph A. (January 3, 2007), "A dynamic survey of graph labeling", Electronic Journal of Combinatorics: DS6, doi:10.37236/27. <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory" (PDF), Studia Sci. Math. Hungar., 1: 215–235. <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are 
 
 
 
 
 
 2
 
 
 ℵ
 
 α
 
 
 
 
 
 
 
 {\displaystyle \scriptstyle 2^{\aleph _{\alpha }}}
 
 friendship graphs of cardinal 
 
 
 
 
 
 ℵ
 
 α
 
 
 
 
 
 {\displaystyle \scriptstyle \aleph _{\alpha }}
 
", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1. <a href="/wiki/V%C3%A1clav_Chv%C3%A1tal" target="_blank">/wiki/V%C3%A1clav_Chv%C3%A1tal</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">Mertzios, George; Walter Unger (2008), "The friendship problem on graphs" (PDF), Relations, Orders and Graphs: Interaction with Computer Science <a href="http://www.dur.ac.uk/george.mertzios/papers/Conf/Conf_Windmills.pdf" target="_blank">http://www.dur.ac.uk/george.mertzios/papers/Conf/Conf_Windmills.pdf</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Huneke, Craig (1 January 2002), "The Friendship Theorem", The American Mathematical Monthly, 109 (2): 192–194, doi:10.2307/2695332, JSTOR 2695332 <a href="/wiki/Doi_(identifier)" target="_blank">/wiki/Doi_(identifier)</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">van der Vekens, Alexander (11 October 2018), "Friendship Theorem (#83 of "100 theorem list")", Metamath mailing list <a href="https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ" target="_blank">https://groups.google.com/forum/#!msg/metamath/j3EjD6ibhvo/ZVlOD3noBAAJ</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Bermond, J.-C.; Brouwer, A. E.; Germa, A. (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, vol. 260, CNRS, Paris, pp. 35–38, MR 0539936. <a href="/wiki/Andries_Brouwer" target="_blank">/wiki/Andries_Brouwer</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">Bermond, J.-C.; Kotzig, A.; Turgeon, J. (1978), "On a combinatorial problem of antennas in radioastronomy", Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Vol. I, Colloq. Math. Soc. János Bolyai, vol. 18, North-Holland, Amsterdam-New York, pp. 135–149, MR 0519261. <a href="/wiki/Anton_Kotzig" target="_blank">/wiki/Anton_Kotzig</a> <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, CiteSeerX 10.1.1.491.974, doi:10.1006/jctb.1995.1026, MR 1328293. <a href="/wiki/Paul_Erd%C5%91s" target="_blank">/wiki/Paul_Erd%C5%91s</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
</ol>

Friendship graph open-in-new

Friendship graph