Freundschaftssatz

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.

Einige Graphen, die die Voraussetzungen des Freundschaftssatzes erfüllen.

Mathematische Formulierung

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

• 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.