##
**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.

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.

Reviewer: H.-J.Presia (Ilmenau)