Freundschaftssatz
Zur Navigation springen
Zur Suche springen
Der Freundschaftssatz ist ein Lehrsatz aus dem mathematischen Gebiet der Graphentheorie. Er besagt anschaulich, dass es in einem Raum, in dem je zwei Personen genau einen gemeinsamen Freund haben, eine Person geben muss, die mit allen befreundet ist. Er wurde 1966 von Erdős, Rényi und Sós bewiesen.
Mathematische Formulierung[Bearbeiten | Quelltext bearbeiten]
Wenn in einem endlichen Graphen je zwei Knoten genau einen gemeinsamen Nachbarn haben, dann gibt es einen Knoten, der zu allen anderen adjazent ist.
Der Freundschaftssatz gilt nicht für unendliche Graphen.
Endliche Graphen, die die Voraussetzungen des Freundschaftssatzes erfüllen, werden auch als Freundschaftsgraphen bezeichnet.
Literatur[Bearbeiten | Quelltext bearbeiten]
- 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.