Eigenvalues of the adjacency matrix of tetrahedral graphs

A tetrahedral graph is defined to be a graphG, whose vertices are identified with the unordered triplets onn symbols, such that vertices are adjacent if and only if the corresponding triplets have two symbols in common. Ifn ₂ (x) denotes the number of verticesy, which are at distance 2 fromx andA(G) denotes the adjacency matrix ofG, thenG has the following properties: P₁) the number of vertices is . P₂)G is connected and regular. P₃)n ₂ (x) = 3/2(n–3)(n–4) for allx inG. P₄) the distinct eigenvalues ofA(G) are –3, 2n–9,n–7, 3(n–3). We show that, ifn > 16, then any graphG (with no loops and multiple edges) having the properties P₁)–P₄) must be a tetrahedral graph. An alternative characterization of tetrahedral graphs has been given by the authors in 1].This research was supported by the National Science Foundation Grant No. GP-5790, and the Army Research Office (Durham) Grant No. DA-ARO-D-31-12-G910. (Institute of Statistics Mimeo Series No. 571, March 1968.)