Graphs in which each pair of vertices has exactly two common neighbours. (English) Zbl 0777.05092

The complete graph \(K_ 4\) possesses the following property: For any two distinct vertices of \(K_ 4\) there exist exactly two vertices which are adjacent to both of them in \(K_ 4\). And Hliněný conjectured that \(K_ 4\) and the direct product \(K_ 4\times K_ 4\) are the only graphs of the class with this property. In the present paper this conjecture is disproved, and the author describes a further finite undirected loopless graph \(G\) without multiple edges which belongs to this class:
Theorem 1. \(G\) is a regular connected graph of degree 6 with 16 vertices which is not isomorphic to \(K_ 4\times K_ 4\).
Moreover some properties of the connected graphs \(G\) of this class are proved, for instance:
Theorem 2. Let \(G\) contain a vertex of degree \(r\geq 5\), then \(G\) is regular of degree \(r\) and its number of vertices is \(n={1\over 2}(r^ 2- r+2)\).
Theorem 3. If \(r\equiv 1\pmod 4\), then no \(G\) exists in the class containing a vertex of degree \(r\).
Finally the following open problem is formulated: Find all graphs of this class.


05C75 Structural characterization of families of graphs
05C40 Connectivity
Full Text: EuDML