The Friendship Theorem states that in a finite graph where every two vertices have exactly one common neighbor, there must exist a single vertex adjacent to every other vertex, meaning the graph consists of a collection of triangles all sharing that one common point. Proved by Paul Erdos, Alfred Renyi and Vera Sos, it is a classical result of extremal graph theory, its name drawn from the informal reading that in a group where every two people share exactly one mutual friend, someone must be everybody's friend.
Facts
StatementThe finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs. 1 Classification
Statement Form Connections
Has Statement Form
In Branch
Source Friendship graph (Wikipedia)
Sources
1. Friendship theorem, Wikipedia
Lead section
the finite graphs with the property that every two vertices have exactly one neighbor in common are exactly the friendship graphs.
Friendship theorem
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.
View the SourceFriendship graph (Wikipedia)
In Branch: Graph Theory, Lead sentenceQuote, In Branch: Graph Theory, Lead sentence
In the mathematical field of graph theory, the friendship graph (or Dutch windmill graph or n-fan) Fn is a planar, undirected grap
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.