Friendship phrase
The friendship theorem is a theorem from the mathematical field of graph theory . It clearly states that in a room in which every two people have exactly one mutual friend, there must be one person who is friends with everyone. It was proven in 1966 by Erdős , Rényi and Sós .
Mathematical formulation
If in a finite graph every two nodes have exactly one common neighbor, then there is one node that is adjacent to all the others .
The friendship theorem does not apply to infinite graphs.
Finite graphs that meet the requirements of the friendship theorem are also known as friendship graphs .
literature
- Erdős, Paul; Rényi, Alfréd; Sós, Vera T. (1966), "On a problem of graph theory", Studia Sci. Math. Hungar. 1: 215-235.