friendship graph

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}}{{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}}. 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.{{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 $\backslash scriptstyle\; 2^\{\backslash aleph\_\backslash alpha\}$ friendship graphs of cardinal $\backslash scriptstyle\backslash aleph\_\backslash alpha$|journal=Canadian Mathematical Bulletin|volume=19|issue=4|year=1976|pages=431–433|doi=10.4153/cmb-1976-064-1|doi-access=free}}.

A combinatorial proof of the friendship theorem was given by Mertzios and Unger.{{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}} Another proof was given by Craig Huneke.{{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}} A formalised proof in Metamath was reported by Alexander van der Vekens in October 2018 on the Metamath mailing list.{{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}}

The friendship graph has chromatic number 3 and chromatic index {{math|2n}}. Its chromatic polynomial can be deduced from the chromatic polynomial of the cycle graph {{math|C{{sub|3}}}} and is equal to

:$(x-2)^n\; (x-1)^n\; x$.

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)}}.{{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}}.{{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}}.

Every friendship graph is factor-critical.

According to extremal graph theory, every graph with sufficiently many edges (relative to its number of vertices) must contain a $k$-fan as a subgraph. More specifically, this is true for an $n$-vertex graph (for $n$ sufficiently large in terms of $k$) if the number of edges is

:$\backslash left\backslash lfloor\; \backslash frac\{n^2\}\{4\}\backslash right\backslash rfloor\; +\; f(k),$

where $f(k)$ is $k^2-k$ if $k$ is odd, and

$f(k)$ is $k^2-3k/2$ if $k$ 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 $n\backslash ge\; 50k^2$), in that for any smaller number of edges there exist graphs that do not contain a $k$-fan.{{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

}}.

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

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

{{reflist}}

Category:Parametric families of graphs

Category:Planar graphs