The friendship graph F8.
The friendship theorem of Paul Erdős, Alfréd Rényi, and Vera T. Sós (1966) 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.
Labeling and colouring
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 k-fan as a subgraph. More specifically, this is true for an n-vertex graph if the number of edges is
where f(k) is k2 − k if k is odd, and f(k) is k2 − 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, in that for any smaller number of edges there exist graphs that do not contain a k-fan.
- Weisstein, Eric W. "Dutch Windmill Graph". MathWorld.
- Gallian, J. A. "Dynamic Survey DS6: Graph Labeling". Electronic J. Combinatorics, DS6, 1-58, Jan. 3, 2007.
- 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.
- Chvátal, Václav; Kotzig, Anton; Rosenberg, Ivo G.; Davies, Roy O. (1976), "There are friendship graphs of cardinal ", Canadian Mathematical Bulletin, 19 (4): 431–433, doi:10.4153/cmb-1976-064-1.
- Mertzios, George; Walter Unger (2008). "The friendship problem on graphs" (PDF). Relations, Orders and Graphs: Interaction with Computer Science.
- Huneke, Craig (1 January 2002). "The Friendship Theorem". The American Mathematical Monthly. 109 (2): 192–194. doi:10.2307/2695332. JSTOR 2695332.
- J.C. Bermond, A. E. Brouwer, and A. Germa, "Systèmes de triplets et différences associées", Problèmes Combinatoires et Théorie des Graphes, Colloq. Intern. du CNRS, 260, Editions du Centre Nationale de la Recherche Scientifique, Paris (1978) 35-38.
- J. C. Bermond, A. Kotzig, and J. Turgeon, On a combinatorial problem of antennas in radioastronomy, in Combinatorics, A. Hajnal and V. T. Sos, eds., Colloq. Math. Soc. János Bolyai, 18, 2 vols. North-Holland, Amsterdam (1978) 135-149.
- 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, doi:10.1006/jctb.1995.1026, MR 1328293.