Research work · 1976
There are 2ℵα Friendship Graphs of Cardinal ℵα
Václav Chvátal, Anton Kotzig, Ivo G. Rosenberg, Roy O. Davies
Canadian Mathematical Bulletin
Abstract
A friendship graph is a graph in which every two distinct vertices have exactly one common neighbour. Finite friendship graphs were characterized by Erdös, Rényi, and Sós [1] as those for which the vertices can be enumerated as u, υ1,…υk, w1,…wk in such a way that the only edges are uυiuwi and υiwi (i = 1,…,k). Thus finite friendship graphs are rather rare. In contrast, we shall show that there are as many nonisomorphic friendship graphs of given infinite cardinal as there are nonisomorphic graphs of that cardinal altogether. In fact, we do a little more.