On the Extendability of Quasi-Strongly Regular Graphs with Diameter 2

Abstract

Let $\ell$ denote a non-negative integer and let $\Gamma$ be a connected graph of even order at least $2 \ell +2$. It is said that $\Gamma$ is $\ell$-extendable if it contains a matching of size $\ell$ and if every such matching is contained in a perfect matching of $\Gamma$. A connected regular graph $\Gamma$ is quasi-strongly regular with parameters $(n, k, \lambda ; \mu _1, \mu _2, \ldots , \mu _s)$, if it is a k-regular graph on n vertices, such that any two adjacent vertices have exactly $\lambda$ common neighbours and any two distinct and non-adjacent vertices have exactly $\mu _i$ common neighbours for some $1 \le i \le s$. The grade of $\Gamma$ is the number of indices $1 \le i \le s$ for which there exist two distinct and non-adjacent vertices in $\Gamma$ with $\mu _i$ common neighbours. In this paper we study the extendability of quasi-strongly regular graphs of diameter 2 and grade 2. In particular, we classify the 2-extendable members of this class of graphs.

1 Introductory Remarks

Throughout this paper graphs are assumed to be finite and simple. We first recall the definition of $\ell$-extendable graphs, introduced in 1980 by Plummer [14]. Let $\ell$ denote a non-negative integer and let $\Gamma$ be a connected graph of even order at least $2 \ell +2$. It is said that $\Gamma$ is $\ell$-extendable if it contains a matching of size $\ell$ and if every such matching is contained in a perfect matching of $\Gamma$. We remark that in his definition from 1980, Plummer did not require an $\ell$-extendable graph to have order at least $2\ell + 2$. But it turns out that this additional assumption is convenient since in this case $\ell$-extendability of $\Gamma$ implies $(\ell - 1)$-extendability of $\Gamma$. Namely, it turns out that if a graph $\Gamma$ of order at least $2\ell + 2$ is $\ell$-extendable, then for any matching M of $\Gamma$ of size $\ell - 1$ we can find an edge of $\Gamma$, which is not incident with any of the edges in M (see [14, Theorem 2.2] for details). Since its introduction in 1980, the family of $\ell$-extendable graphs has been studied from various points of view, see for instance [16] for a survey of results on extendability prior to 1994, [1, 2, 12] for results on extendability of Cayley graphs, and [10, 15, 17,18,19] for various other results on the topic.

Considerable attention was given to the study of extendability of various families of highly regular graphs. For example, the extendability of the well known family of strongly regular graphs was considered in [3, 9, 11]. Recall that a connected graph $\Gamma$ is strongly regular with parameters $(n,k,\lambda ,\mu )$ if $\Gamma$ is a k-regular graph on n vertices such that any two adjacent (distinct and nonadjacent, respectively) vertices have exactly $\lambda$ ($\mu$, respectively) common neighbours. It was proved in [9] that each strongly regular graph of even order $n \ge 4$ is 1-extendable. Moreover, it was proved in [9, 11] that there are only three strongly regular graphs of even order, which are not 2-extendable (see Proposition 2.3). The extendability of distance-regular graphs, which are a generalization of strongly regular graphs, was studied in [4].

The diameter of a connected strongly regular graph, which is not complete, is of course 2. Therefore, it seems natural to consider extendability of other regular graphs of diameter 2. For example, the extendability of Deza graphs, where we only insist that there exist two numbers such that for any pair of distinct vertices the number of their common neighbours equals one of those two numbers, was studied in [13] where it was proved that, apart from three strongly regular graphs of even order there is just one more non-2-extendable Deza graph of even order and diameter 2, namely the complement of the Möbius ladder on eight vertices.

The most important facts, on which the proofs of the results from [9, 11, 13] rely, are the regularity of the graph, the fact that its diameter equals 2 and the existence of the parameter $\lambda$. A regular graph is edge-regular if there exists a constant $\lambda$ such that any pair of adjacent vertices share $\lambda$ common neighbours. Therefore, each strongly regular graph is edge-regular. It thus seems natural to consider the following problem.

Problem 1.1

Classify the 2-extendable edge-regular graphs (of even order) and diameter 2.

The aim of this paper is to make the next step towards the solution of this problem. We focus on another generalization of strongly regular graphs, namely on the quasi-strongly regular graphs, which were studied to some extent in [7]. A quasi-strongly regular graph with parameters $(n, k, \lambda ; \mu _1, \mu _2, \ldots , \mu _s)$, where $\mu _1> \mu _2> \cdots > \mu _s$, is a k-regular graph on n vertices such that any two adjacent vertices have $\lambda$ common neighbours (and so $\Gamma$ is edge-regular) and any two distinct and non-adjacent vertices have $\mu _i$ common neighbours for some $1 \le i \le s$. The grade of $\Gamma$ is the number of indices $1 \le i \le s$, for which there exists a pair of distinct and non-adjacent vertices in $\Gamma$ with $\mu _i$ common neighbours. A quasi-strongly regular graph with parameters $(n, k, \lambda ; \mu _1, \mu _2, \ldots , \mu _s)$ is proper if its grade equals s. Note that in such a case the graph is connected with diameter 2 if and only if $\mu _i \ge 1$ for all $1 \le i \le s$.

Note that each edge-regular graph is quasi-strongly regular of some grade. In this paper we study the extendability of quasi-strongly regular graphs of grade (at most) 2 with parameters $(n, k, \lambda ; \mu _1, \mu _2)$, for which $\mu _1 > \mu _2 \ge 1$. Observe that such a graph has diameter 2 provided it is not complete, and is strongly regular if and only if it is of grade 1. Our main result is the following theorem.

Theorem 1.2

Let $\Gamma$ be a quasi-strongly regular graph with parameters $(n, k, \lambda ;\mu _1, \mu _2)$, $n \ge 6$ even, $\mu _1 > \mu _2 \ge 1$. Then $\Gamma$ is not 2-extendable if and only if it is isomorphic to one of the following graphs:

• the complete multipartite graph $K_{2,2,2}$ (which is strongly regular with parameters (6, 4, 2, 4));

• the Möbius ladder on eight vertices (which is a proper quasi-strongly regular graph with parameters (8, 3, 0; 2, 1));

• the Petersen graph (which is strongly regular with parameters (10, 3, 0, 1));

• the lexicographic product $C_5[2K_1]$ of the cycle $C_5$ on five vertices with the edgeless graph on two vertices (which is a proper quasi-strongly regular graph with parameters (10, 4, 0; 4, 2)).

Fig. 1

The four non-2-extendable graphs from Theorem 1.2

The four graphs from Theorem 1.2 are depicted on Fig. 1.

2 Preliminaries

In this section we first fix some notation and then gather various results from the literature that will be used in the remainder of the paper.

Let $\Gamma$ be a connected graph with vertex set $V = V(\Gamma )$ and let $v \in V$. The distance of v from a vertex $u \in V$ will be denoted by d(u, v). For a non-negative integer i, we denote by $N_i(v) = \{u \in V :d(u,v) = i\}$ the set of all vertices of $\Gamma$ at distance i from v. We abbreviate $N_1(v)$ by N(v). The fact that the vertices u and v are adjacent in $\Gamma$ will be denoted by $u \sim v$. For a subset $S \subseteq V$ we let $\Gamma - S$ be the subgraph of $\Gamma$ induced on the set $V {\setminus } S$.

Let $\Gamma _1$ and $\Gamma _2$ be graphs. The lexicographic product of $\Gamma _1$ by $\Gamma _2$, denoted by $\Gamma _1[\Gamma _2]$, is the graph whose vertex set is the cartesian product $V(\Gamma _1) \times V(\Gamma _2)$ with vertices $(u_1,u_2)$ and $(v_1, v_2)$ being adjacent if and only if either $u_1$ is adjacent with $v_1$ in $\Gamma _1$, or $u_1 = v_1$ and $u_2$ is adjacent with $v_2$ in $\Gamma _2$. We will denote the complete graph, the empty graph and the cycle on n vertices by $K_n$, $E_n$ and $C_n$, respectively.

Let us now state some results from the literature that we will need in the remainder of the paper. The first two are about all regular graphs of diameter 2.

Lemma 2.1

([13, Lemma 2.1]) Let $\Gamma$ be a regular graph of valency k, even order and diameter 2. Let $S \subseteq V$ be such that $\Gamma -S$ is not connected and let C be a component of $\Gamma -S$. Then there are at least k edges between C and S in $\Gamma$.

Proposition 2.2

([8, Theorem 1.3], [13, Theorem 2.2, Theorem 2.3]) Let $\Gamma$ be a regular graph of even order and diameter 2. Then $\Gamma$ is both 0- and 1-extendable.

We also record the result of [9, 11] on the extendability of strongly regular graphs.

Proposition 2.3

Let $\Gamma$ be a strongly regular graph of even order which is not 2-extendable. Then $\Gamma$ is either the cycle $C_4$ on four vertices (of valency 2), or the Petersen graph (of valency 3), or the complete tripartite graph $K_{2,2,2}$ (of valency 4).

The general idea of the proof of Theorem 1.2 is similar to the one used in [11] ([13], respectively) for strongly regular graphs (Deza graphs, respectively) of even order. One of the key factors in the proof of Theorem 1.2 is the classical result of Tutte from 1947 giving a necessary and sufficient condition for a graph to contain a perfect matching. To state it we first need to fix some additional notation. Connected components of a graph $\Gamma$ will simply be called components of $\Gamma$. A component C of $\Gamma$ is called even (odd, respectively), if the cardinality of C is even (odd, respectively). The number of odd components of $\Gamma$ will be denoted by $o(\Gamma )$. We can now state the above mentioned result of Tutte.

Theorem 2.4

([5, Theorem 2.2.1]) A graph $\Gamma$ has a perfect matching if and only if for every subset $S \subseteq V(\Gamma )$ we have $o(\Gamma -S) \le |S|$.

When dealing with $\ell$-extendability the following corollary of Theorem 2.4 is of use. The result was implicitly proved in [18, Theorem 2.2], but we include a short proof for the convenience of the reader.

Proposition 2.5

Let $\ell \ge 1$ be an integer and let $\Gamma$ be a connected graph of order at least $2\ell + 2$ containing a perfect matching. Then the graph $\Gamma$ is not $\ell$-extendable if and only if it contains a subset S of vertices such that the subgraph induced by S contains $\ell$ independent edges and $o(\Gamma - S) \ge |S| - 2\ell + 2$.

Proof

Suppose first there exists a set of $\ell$ independent edges of $\Gamma$ that cannot be extended to a perfect matching of $\Gamma$ and let $S_0$ be the set of their endvertices. Then $\Gamma - S_0$ does not contain a perfect matching, and so Theorem 2.4 implies there exists a subset $S' \subset V(\Gamma -S_0)$ such that $o((\Gamma -S_0)-S') > |S'|$. Setting $S = S_0 \cup S'$ we have $|S| = |S'|+2\ell$, and so clearly $o(\Gamma -S) = o((\Gamma -S_0)-S') > |S| - 2\ell$ holds. As $\Gamma$ is of even order $o(\Gamma -S)$ and |S| are of the same parity, implying that $o(\Gamma -S) \ge |S|-2\ell +2$.

Conversely, suppose S is a set satisfying the assumptions of the proposition and write S as a disjoint union $S_0 \cup S'$, where $S_0$ consists of the endvertices of $\ell$ independent edges. Then $o((\Gamma -S_0)-S') = o(\Gamma -S) \ge |S'| + 2$, and thus $\Gamma - S_0$ does not have a perfect matching by Theorem 2.4. It follows that the chosen set of $\ell$ independent edges cannot be extended to a perfect matching of $\Gamma$. $\square$

When searching for the largest $\ell$ for which the graph is still $\ell$-extendable one can use the following corollary, which will be the main ingredient of our proofs throughout the paper.

Corollary 2.6

Let $\ell \ge 1$ be an integer and let $\Gamma$ be an $(\ell -1)$-extendable connected graph of order at least $2\ell + 2$. Then $\Gamma$ is not $\ell$-extendable if and only if it contains a subset S of vertices such that the subgraph induced by S contains $\ell$ independent edges and $o(\Gamma - S) = |S| - 2\ell + 2$.

Proof

If there exists $S \subseteq V(\Gamma )$ such that the subgraph induced by S contains $\ell$ independent edges and $o(\Gamma - S) = |S| - 2\ell + 2$, then $\Gamma$ is not $\ell$-extendable by Proposition 2.5. Assume now that $\Gamma$ is not $\ell$-extendable. By Proposition 2.5, there exists $S \subseteq V(\Gamma )$ such that the subgraph induced by S contains $\ell$ independent edges and $o(\Gamma - S) \ge |S| - 2\ell + 2$. On the other hand, since $\Gamma$ is $(\ell -1)$-extendable, Proposition 2.5 implies that $o(\Gamma - S) < |S| - 2(\ell -1) + 2 = |S| - 2\ell + 4$. But as $\Gamma$ is of even order, $o(\Gamma - S)$ and |S| are of the same parity, and so $o(\Gamma - S) = |S| - 2\ell + 2$ must hold. $\square$

We finish this section with a nice result by Goldberg on quasi-strongly regular graphs of grade 2. Let $\Gamma$ be a proper quasi-strongly regular graph with parameters $(n,k,\lambda ;\mu _1,\mu _2)$, where $\mu _1 > \mu _2 \ge 1$. Let v be a vertex of $\Gamma$ and let $t_1(v)$, $t_2(v)$ denote the number of non-neighbours of v, different from v, that share $\mu _1$ or $\mu _2$ common neighbours with v, respectively.

Proposition 2.7

([7, Theorem 2.1]) Let $\Gamma$ be a proper quasi-strongly regular graph with parameters $(n,k,\lambda ;\mu _1,\mu _2)$, where $\mu _1 > \mu _2 \ge 1$. Then the numbers $t_1(v)$ and $t_2(v)$ do not depend on v and writing $t_1 = t_1(v)$ and $t_2 = t_2(v)$ we have:

$$\begin{aligned} t_1 = {k(k-\lambda -1)-\mu _2(n-k-1) \over \mu _1 - \mu _2}, \quad t_2 = {\mu _1(n-k-1) - k(k-\lambda -1) \over \mu _1 - \mu _2}. \end{aligned}$$

Moreover, $1 \le t_1, t_2 \le n-k-2$.

3 The Graphs of Valency At Most 4

It proves convenient to analyze the regular graphs of diameter 2 and valency at most 4 separately. The cubic ones are particularly easy to deal with since there is only a handful of graphs to consider (see [13, Theorem 3.1]).

Theorem 3.1

The five graphs from Fig. 2 are the only cubic graphs of diameter 2. The only 2-extendable graph among them is the complete bipartite graph $K_{3,3}$ and the only quasi-strongly regular graphs among them are the complete bipartite graph $K_{3,3}$, the Petersen graph (which are both strongly regular) and the Möbius ladder on eight vertices (which is a proper quasi-strongly regular graph with parameters (8, 3, 0; 1, 2)). As a consequence, the Möbius ladder on eight vertices is the only cubic non-2-extendable quasi-strongly regular graph of diameter 2, which is not strongly regular.

Proof

That the five graphs from Fig. 2 are the only cubic graphs of diameter 2 follows from [13, Theorem 3.1]. The other claims are easy to check. $\square$

Fig. 2

The five cubic graphs of diameter 2

We now focus on the more challenging case of quartic graphs of diameter 2. We in fact first classify all quasi-strongly regular graphs with parameters $(n,4,\lambda ;\mu _1, \mu _2)$ with n even and $\mu _1 > \mu _2 \ge 1$. We do this in two steps, the first of which is to show that apart from three well known graphs the only other possible such graphs are of order 14 with $\mu _1 = 2$ and $\mu _2 = 1$.

Lemma 3.2

Let $\Gamma$ be a quasi-strongly regular graph with parameters $(n,4,\lambda ;\mu _1, \mu _2)$ with n even and $\mu _1 > \mu _2 \ge 1$. Then $\Gamma$ is the complete multipartite graph $K_{2,2,2}$, the complete bipartite graph $K_{4,4}$, the lexicographic product $C_5[E_2]$, or it is a proper quasi-strongly regular graph with parameters (14, 4, 0; 2, 1).

Proof

Observe first that since $\Gamma$ is of diameter 2 and valency 4, the fact that n is even implies $n \le 16$. We divide our proof into three cases depending on the value of $0 \le \lambda \le 2$ (note that $\lambda = 3$ would imply $\Gamma = K_5$, contradicting the assumption that n is even).

Case $\lambda = 2$: Pick an edge uv of $\Gamma$, let $N(u) \cap N(v) = \{w_1, w_2\}$ and denote the remaining neighbours of u and v by x and y, respectively. Since x and u have two common neighbors $x \sim w_1, w_2$ and similarly $y \sim w_1, w_2$. It is now clear that for x and $w_1$ to have two common neighbors $x \sim y$ has to hold, and so $\Gamma = K_{2,2,2}$.

Case $\lambda = 1$: Note that this implies that for each $v \in V(\Gamma )$ the subgraph of $\Gamma$, induced on N(v), is $2K_2$. Moreover, observe that for any $v \in V(\Gamma )$ each $w \in N_2(v)$ has at most two neighbours in N(v) (otherwise there would be an adjacent pair of vertices in N(v) having both v and w as common neighbors, contradicting $\lambda = 1$). Since the number of edges between N(v) and $N_2(v)$ is clearly $4\cdot 2 = 8$, this proves that $|N_2(v)| \le 8 \le 2|N_2(v)|$, and so the fact that $n = 1 + 4 + |N_2(v)|$ is even implies $n \in \{10, 12\}$. Then $\Gamma$ cannot be strongly regular since counting the edges between N(v) and $N_2(v)$ again would force $8 = \mu |N_2(v)|$, contradicting the fact that $|N_2(v)|$ must be odd. By [7, Section 7] it thus follows that no graph $\Gamma$, corresponding to Case 1, exists.

Case $\lambda = 0$: Pick a vertex $v \in V(\Gamma )$ and note that every vertex of N(v) has three neigbours in $N_2(v)$, so that there are exactly 12 edges between N(v) and $N_2(v)$. If all vertices of $N_2(v)$ have the same number of neighbours in N(v) then the fact that n is even implies $|N_2(v)| = 3$, and so $\Gamma = K_{4,4}$. For the remainder of the proof we can thus assume that $\Gamma$ is of grade 2 and that $n \ge 10$. Consequently, Proposition 2.7 implies that since $t_1 \ge 1$ and n is even, the only possibility for $\mu _2 > 1$ to hold is if $\mu _2 = 2$, $n = 10$ and $\mu _1 \in \{3,4\}$, which by [7, Section 7] implies that $\mu _1 = 4$ and $\Gamma = C_5[E_2]$. We are thus left with the possibility that $\mu _2 = 1$. By [7, Section 7] we cannot have $n \le 12$, and so $n \in \{14, 16\}$. It was proved in [6] that the only graph with diameter 2, maximal valency k and of order $n=k^2$ is isomorphic to $C_4$. This shows that $n=14$ has to hold. By Proposition 2.7, we have $t_1=3/(\mu _1-1)$, and so $\mu _1 \in \{4,2\}$. If $\mu _1 = 4$, then $t_1 = 1$, and so there is a unique $w \in N_2(v)$ such that $N(w) = N(v)$. But then each vertex from N(v) has at least three other vertices with which it shares at least two neighbors, contradicting the fact that $\mu _2 = 1$ and $t_1 = 1$. This finally proves that $\mu _1 = 2$, as claimed. $\square$

To complete the above mentioned classification we now prove that the last possibility from the above lemma in fact cannot occur.

Theorem 3.3

The only quasi-strongly regular graphs of diameter 2 and valency 4 with parameters $(n,4,\lambda ;\mu _1, \mu _2)$ with n even and $\mu _1 > \mu _2 \ge 1$ are the complete multipartite graph $K_{2,2,2}$ (which is strongly regular with parameters (6, 4, 2, 4)), the complete bipartite graph $K_{4,4}$ (which is strongly regular with parameters (8,4,0,4)) and the lexicographic product $C_5[E_2]$ (which is a proper quasi-strongly regular graph with parameters (10, 4, 0; 4, 2)).

Proof

By Lemma 3.2 and its proof we only need to prove that there is no proper quasi-strongly regular graph with parameters (14, 4, 0; 2, 1). By way of contradiction suppose $\Gamma$ is such a graph. By Proposition 2.7, we have $t_1 = 3$ and $t_2 = 6$. Pick a vertex $v \in V(\Gamma )$ and denote $U = N(v) = \{u_1, u_2, u_3, u_4\}$ and $N_2(v) = W \cup Z$, where $W = \{w_1, w_2, \ldots , w_6\}$ and $Z = \{z_1, z_2, z_3\}$, where each of $w_i$ has one common neighbour with v while each of $z_j$ has two. Observe that since $\mu _1 = 2$ each pair of vertices from U can be adjacent to at most one of the vertices from Z. We distinguish three cases depending on whether each vertex of U is adjacent to at least one from Z and on whether there is some $u_i \in U$ which is adjacent to the whole Z.

Case 1: Some $u_i \in U$ is adjacent to the whole Z.

With no loss of generality assume $u_4 \sim z_j$ for all $1 \le j \le 3$, $u_i \sim z_i$ for $1 \le i \le 3$, and then $u_i \sim w_{2i-1}, w_{2i}$, for $1 \le i \le 3$. In this case $u_1$, $u_2$ and $u_3$ are the three vertices from $N_2(u_4)$, each having two common neighbours with $u_2$, and so each of $w_i \in W$ has exactly one neighbour in Z. Since $w_1 \not \sim z_1$ (recall that $\lambda = 0$), we can further assume $w_1 \sim z_2$. For $d(u_1,z_3) \le 2$ to hold we thus have $w_2 \sim z_3$. Since none of $w_3$ and $w_4$ can be adjacent to $z_2$ and only one neighbour of $z_3$ has not been determined yet, we can further assume $w_3 \sim z_1$. For $d(u_2,z_3) \le 2$ to hold this forces $w_4 \sim z_3$. Hence $d(w_1,z_3), d(w_3,z_3) \le 2$ forces $w_1 \sim w_4$ and $w_2 \sim w_3$. The only two vertices of W for which their unique neighbour in Z has not yet been determined are $w_5$ and $w_6$, and so we can assume $w_5 \sim z_1$ and $w_6 \sim z_2$. But then $d(w_4, z_1), d(w_5, z_2) \le 2$ force $w_4 \sim w_5$ and $w_1 \sim w_5$, respectively, giving rise to the 3-cycle $(w_1, w_4, w_5)$.

Case 2: Some $u_i \in U$ has no neighbours in Z.

With no loss of generality assume $u_4$ has no neighbours in Z while $u_1 \sim z_1, z_2$, $u_2 \sim z_2, z_3$ and $u_3 \sim z_1, z_3$. We can then also assume that $u_4 \sim w_i$ for $4 \le i \le 6$ and $u_j \sim w_j$ for all $1 \le j \le 3$. Now, $d(u_2, z_1), d(u_3, z_2), d(u_1, z_3) \le 2$ force $w_2 \sim z_1$, $w_3 \sim z_2$ and $w_1 \sim z_3$, respectively. For $d(z_i, u_4) \le 2$ to hold for each of $1 \le i \le 3$, each of the vertices from Z is adjacent to one of $w_4, w_5$ and $w_6$, with no loss of generality assume $z_1 \sim w_4$. Moreover, the three vertices in $N_2(u_4)$ that each share two neighbours with $u_4$ can only be $w_1, w_2$ and $w_3$, and so $w_2$ must be adjacent to $w_5$ and $w_6$ (since $w_2 \sim w_4$ would introduce the 3-cycle $(w_2, z_1, w_4)$). For $d(u_1,w_5), d(u_1,w_6) \le 2$ to hold at least one of $w_5, w_6$ has to be adjacent to $w_1$, so we can assume $w_1 \sim w_6$. Then $d(u_3, w_6) \le 2$ implies $w_3 \sim w_6$ (as $z_3 \sim w_6$ would introduce a 3-cycle). It is now clear that the only vertices that could possibly have two common neighbours with $w_6$ are $z_2, z_3, w_4$ and $w_5$, so at least one of them is $z_2$ or $z_3$. But for each of them the remaining neighbour is one of $w_4$ and $w_5$, contradicting $t_1 = 3$.

Case 3: For each $u_i \in U$ we have $|N(u_i) \cap Z| \in \{1,2\}$.

Clearly two of the vertices from U have two neighbours in Z while the other two have one. With no loss of generality we can assume $N(u_1) \cap N_2(v) = \{w_1, w_2, z_1\}$, $N(u_2) \cap N_2(v) = \{w_3, z_1, z_2\}$, $N(u_3) \cap N_2(v) = \{w_4, z_2, z_3\}$ and $N(u_4) \cap N_2(v)= \{w_5, w_6, z_3\}$. For $d(u_1, z_2), d(u_4,z_2) \le 2$ to hold $z_2$ must be adjacent to one of $w_1, w_2$ and to one of $w_5, w_6$. We can assume $z_2 \sim w_1, w_6$. Then $d(w_2, z_2), d(w_5, z_2) \le 2$ force $w_1 \sim w_5$ and $w_2 \sim w_6$. Since each of $w_2 \sim z_1$ and $w_5 \sim z_3$ would produce a 3-cycle, $d(u_2,w_2), d(u_3, w_5) \le 2$ force $w_2 \sim w_3$ and $w_4 \sim w_5$, respectively. Observe that for $\lambda = 0$ to hold the remaining neighbour of $w_1$ must be one of $w_3$ and $z_3$, while the remaining neighbour of $w_6$ must be one of $z_1$ and $w_4$.

Now, if $w_1 \sim w_3$ then $d(w_1, z_3) \le 2$ forces $w_3 \sim z_3$, and consequently the remaining neighbour of $z_3$ is $z_1$. But then $d(u_3, w_2) \le 2$ forces $w_2 \sim w_4$, so that $w_6 \not \sim w_4$, and so $w_6 \sim z_1$, which leaves $w_4$ of valency 3, a contradiction. We thus must have $w_1 \sim z_3$. Now, each of $w_2, w_3$ and $z_1$ must have a common neighbour with $u_3$, and so one of them is adjacent to $z_3$ and two to $w_4$. Since $w_2 \sim w_3$ this forces $z_1 \sim w_4$. Then $d(u_2, z_3) \le 2$ implies that $z_3$ is adjacent to one of $w_3$ and $z_1$. But $z_3 \sim w_3$ would imply that $d(z_1, z_3) > 2$ as $z_1 \not \sim w_1, w_3$, and so $z_1 \sim z_3$ must hold. However, then $d(u_3, w_2) \le 2$ forces $w_2 \sim w_4$, leaving $w_6$ to be of valency 3, a contradiction. $\square$

We can now classify all non-2-extendable quasi-strongly regular graphs with parameters $(n,4,\lambda ; \mu _1, \mu _2)$, where n is even and $\mu _1 > \mu _2 \ge 1$.

Theorem 3.4

The only non-2-extendable quasi-strongly regular graphs with parameters $(n,4,\lambda ;\mu _1, \mu _2)$, where n is even and $\mu _1 > \mu _2 \ge 1$ are the complete bipartite graph $K_{2,2,2}$ (which is strongly regular with parameters (6, 4, 2, 4)) and the lexicographic product $C_5[E_2]$ (which is a proper quasi-strongly regular graph with parameters (10, 4, 0; 4, 2)).

Proof

By Theorem 3.3 we only need to consider the graphs $K_{2,2,2}$, $K_{4,4}$ and $C_5[E_2]$. It is easy to see that $K_{4,4}$ is 2-extendable while $K_{2,2,2}$ is not (see also [11]). As for $C_5[E_2]$ one can easily find a pair of disjoint edges that do not extend to a perfect matching, proving that this graph is not 2-extendable (note that, since $C_5[E_2]$ is isomorphic to the Cayley graph of $\mathbb {Z}_{10}$ with respect to the connection set $\{\pm 1, \pm 4\}$ this also follows from [1]). $\square$

4 Odd Components

For the rest of this paper let $\Gamma$ denote a quasi-strongly regular graph with parameters $(n,k,\lambda ;\mu _1, \mu _2)$, where n is even, $k \ge 5$ and $\mu _1 > \mu _2 \ge 1$. The proof that $\Gamma$ is 2-extendable is by contradiction. From now on we thus assume that $\Gamma$ is not 2-extendable (recall that, by Proposition 2.2, it is 1-extendable). Note that, by Proposition 2.3, $\Gamma$ is not strongly regular, so we can assume in addition that $\Gamma$ is of grade 2. It follows from Corollary 2.6 that we can find a vertex subset S containing two independent edges such that $o(\Gamma -S)=|S|-2$. The aim of this section is to prove that each odd component of $\Gamma -S$ must be a singleton (see Proposition 4.5).

Now, take S as in the previous paragraph and suppose $\Gamma - S$ has an even component C. Pick $x \in C$ and set $S' = S \cup \{x\}$. Observe that each component of $\Gamma - S$, different from C, is also a component of $\Gamma - S'$. The remaining components of $\Gamma - S'$ are the components of the subgraph of $\Gamma$, induced on $C {\setminus } \{x\}$. Since this set is of odd size at least one of them is odd. Thus $o(\Gamma - S') \ge o(\Gamma - S) + 1 = |S| - 1 = |S'| - 2$. However, as $\Gamma$ is 1-extendable and $o(\Gamma - S')$ and $|S'|$ are of the same parity, Proposition 2.5 implies that in fact $o(\Gamma - S') = |S'| - 2$ holds. Repeating this process of enlarging S until no even component of $\Gamma - S$ exists we can thus eliminate all even components of $\Gamma - S$. For the rest of the paper we can thus assume that $\Gamma - S$ has no even components. For future reference we also name the endvertices of the chosen two independent edges within the subgraph of $\Gamma$ induced on S.

Hypothesis 4.1

Let $\Gamma$ be a non-2-extendable proper quasi-strongly regular graph with parameters $(n,k,\lambda ;\mu _1, \mu _2)$, where n is even, $k \ge 5$ and $\mu _1 > \mu _ 2 \ge 1$. Furthermore, let $S \subseteq V(\Gamma )$ be such that the subgraph of $\Gamma$ induced on S contains independent edges $u_1v_1$ and $u_2v_2$, that $\Gamma - S$ has no even components and that $o(\Gamma -S) = |S| - 2$.

Observe that, since $|S|\ge 4$, there are at least two (odd) components of $\Gamma - S$, and so each $v \in V(\Gamma ) {\setminus } S$ has at least one neighbour in S (otherwise the diameter of $\Gamma$ is not 2). We next prove that, in fact, v has at least two neighbours in S.

Lemma 4.2

Under Hypothesis 4.1, every vertex in $\Gamma - S$ has at least two neighbours in S.

Proof

Suppose on the contrary that there is a vertex v in $\Gamma - S$, which has just one neighbour, say u, in S. Let C denote the odd component containing v. Since $N(v) {\setminus } \{u\} \subseteq C$ we have $|C| \ge 5$ (recall that $k \ge 5$). Let $C_1, C_2, \ldots , C_{|S|-3}$ denote the other (odd) components of $\Gamma -S$ and let $m_i = |C_i|$ for $1 \le i \le |S|-3$. Without loss of generality assume $m_1 \le m_2 \le \cdots \le m_{|S|-3}$. Since for each $1 \le i \le |S|-3$ the vertex v must have a common neighbour with each $w \in C_i$, the vertex u must be adjacent to all of the vertices in $C_1 \cup C_2 \cup \cdots \cup C_{|S|-3}$ and clearly $\mu _2 = 1$ holds. Moreover, u and v have $\lambda$ common neighbours, which are of course all contained in C. We therefore have

$$\begin{aligned} k \ge |N(u) \cap S| + 1 + m_1 + m_2 + \cdots + m_{|S|-3} + \lambda . \end{aligned}$$

(1)

On the other hand, for every vertex $w \in C_1$ we have $N(w) \subseteq C_1 \cup S$, implying

$$\begin{aligned} k \le m_1 - 1 + |S|. \end{aligned}$$

(2)

We split our analysis into two cases depending on whether $|S| = 4$ or not.

Case 1: $|S|=4$, that is, $S = \{u_1, v_1, u_2, v_2 \}$.

Since u has at least one neighbour in S, (1) and (2) yield

$$\begin{aligned} 2 + m_1 + \lambda \le k \le m_1 + 3. \end{aligned}$$

(3)

It follows that each $w \in C_1$ has at least $3 + \lambda$ neighbours in S, and so is a common neighbour of $u_1$ and $v_1$ or of $u_2$ and $v_2$ (or both), implying that $\lambda \ge 1$. But then (3) implies $\lambda = 1$, which in turn implies that each $w \in C_1$ is adjacent to entire S. Then $m_1 = 1$ (as otherwise $u_1$ and $v_1$ have more than one common neighbour), contradicting $k \ge 5$.

Case 2: $|S| \ge 5$.

Observe that (1) and (2) imply $|S| \ge 2 + m_2 + \cdots + m_{|S|-3} + \lambda \ge |S|-3 + m_{|S|-3} + \lambda$. This implies that if $m_{|S|-3} \ne 1$ we must have $m_{|S|-3} = 3$, $m_{|S|-4} = 1$ and $\lambda = 0$. But then (1) implies $k \ge |S|$, forcing the unique vertex of $C_1$ to be adjacent to entire S, which contradicts $\lambda = 0$. This shows that $m_1 = m_2 = \cdots = m_{|S|-3} = 1$. Combining together (1) and (2) we thus get

$$\begin{aligned} |S| \ge k \ge |N(u) \cap S| + |S| - 2 + \lambda . \end{aligned}$$

(4)

For each $1 \le i \le |S|-3$ denote the unique vertex of $C_i$ by $w_i$. Now, if $\lambda \ne 0$ then for u and $w_1$ to have a common neighbour, $|N(u) \cap S| \ge 1$ must hold, and so (4) implies $\lambda = |N(u) \cap S| = 1$ and $k = |S|$. But then both $w_1$ and $w_2$ are common neighbours of $u_1$ and $v_1$, contradicting $\lambda = 1$. Thus $\lambda = 0$, and so (4) forces $k = |S|-2$ (and consequently u has no neighbours in S), since otherwise one of $u_1$ and $v_1$ or $u_2$ and $v_2$ would both be adjacent to $w_1$. We thus have $N(u) = \{v\} \cup \{w_i :1 \le i \le |S|-3\}$, implying that v is adjacent to all other vertices of C (otherwise u has no common neighbour with such a vertex of C). Thus $|C| = k$ and so $\lambda = 0$ implies that each vertex of C, other than v, has $k-1$ neighbours in S. Finally, take $x \in S {\setminus } \{u,u_1,v_1,u_2,v_2\}$ (note that $|S| = k+2 \ge 7$) and observe that $\lambda = 0$ implies that x is adjacent to all of $w_i$, $1 \le i \le |S|-3$. But since each $w \in C {\setminus } \{v\}$ can also be adjacent to at most one of $u_1, v_1$ and at most one of $u_2, v_2$, the fact that it is not adjacent to u implies that also $x \sim w$. Thus x has at least $|S|-3+k-1 = 2k-2$ neighbours, a contradiction. $\square$

Lemma 4.3

Under Hypothesis 4.1, suppose C is a component of $\Gamma -S$ which is not a singleton. Then there are more than 3k / 2 edges between C and S.

Proof

Denote $m = |C|$ and note that $m \ge 3$. Let t be the number of edges between C and S. By Lemma 4.2, we have $t \ge 2m$, and so if $k \le m+1$, the fact that $k \ge 5$ implies $t \ge 2m \ge 2(k-1) > 3k/2$.

We are left with the possibility that $k \ge m+2$. Since each vertex of C is adjacent to at least $k - (m-1)$ vertices of S, we thus have $t \ge m(k - (m-1))$, and so

$$\begin{aligned} t - {3k \over 2}\ge & {} mk - m(m-1) - {3k \over 2} = \left( m - {3 \over 2}\right) k - m(m-1)\\\ge & {} \left( m - {3 \over 2}\right) (m+2)-m(m-1) = {3 m \over 2} - 3 \ge {9 \over 2} - 3 > 0, \end{aligned}$$

as claimed. $\square$

We can now finally prove that all of the components of $\Gamma - S$ are singletons. We do this in two steps.

Lemma 4.4

Under Hypothesis 4.1, $\Gamma -S$ has at most one component which is not a singleton.

Proof

Suppose that $\Gamma -S$ has at least two (odd) components, say $C_1$ and $C_2$ with cardinalities at least 3. Without loss of generality we can assume that $m_1 = |C_1| \le m_2 = |C_2|$. Now, each vertex of $C_1$ has at least $k - (m_1 - 1)$ neighbours in S, and so there are at least $k m_1 - m_1(m_1-1)$ edges between $C_1$ and S. Let t denote the number of edges between S and $V(\Gamma ) {\setminus } S$ and note that $t \le k|S| - 4$. If $k \ge m_1+2$, then Lemmas 2.1 and 4.3 imply

$$\begin{aligned} t> & {} k m_1 - m_1(m_1-1) + {3k \over 2} + k(|S|-4) = k\left( m_1-{5 \over 2}\right) - m_1(m_1-1) + k|S| \\\ge & {} (m_1+2)\left( m_1-{5 \over 2}\right) - m_1(m_1-1) + k|S| = {m_1 \over 2}+k|S|-5 > k|S|-4, \end{aligned}$$

a contradiction.

Therefore, $k \le m_1+1$. Recall that, by Lemma 4.2, each vertex of $C_1 \cup C_2$ has at least two neighbours in S. Using this we find that

$$\begin{aligned} k|S| - 4 \ge t \ge 2m_1 + 2m_2 + k(|S|-4) \ge 4m_1 + k(|S|-4), \end{aligned}$$

(5)

which implies $k \ge m_1 + 1$, and consequently $k = m_1+1$ (yielding $m_1 \ge 5$). Moreover, equalities must hold in (5), and so there are exactly two edges in S, $m_1=m_2$ holds, each vertex in $C_1 \cup C_2$ has exactly two neighbours in S, and there are exactly k edges between any other component of $\Gamma -S$ and S. By Lemma 4.3, all other components of $\Gamma -S$ are singletons. Denote the corresponding vertices by $w_3, \ldots , w_{|S|-2}$.

Now, observe that $k = m_1 + 1$ and the fact that each vertex of $C_1 \cup C_2$ has two neighbours in S implies that the components $C_1$ and $C_2$ are both complete graphs $K_{m_1}$, and so $\lambda \ge m_1 - 2 \ge 3$. This implies $|S| = 4$, since otherwise the singleton $w_3$ would have common neighbours with at least one u in $S {\setminus } \{u_1, v_1, u_2, v_2\}$ which would necessarily have to be in S, contradicting the fact that there are just two edges in S. Note that any pair of vertices of $C_1$ has the same number $\lambda _S = \lambda - (m_1 - 2)$ of common neighbours in S. Since $|S| = 4$ and $m_1 \ge 5 > 2$, we have $\lambda _S \ne 0$, and so it is easy to see that $m_1 \ge 5$ implies $\lambda _S = 2$. But then $\lambda = m_1 = k - 1$, and so $\Gamma$ is a complete graph, contradicting the fact that $\Gamma$ is of grade 2. $\square$

Proposition 4.5

Under Hypothesis 4.1, all of the components of $\Gamma -S$ are singletons.

Proof

Suppose to the contrary that $\Gamma -S$ has a component with cardinality at least 3 (recall that $\Gamma -S$ has no even components). By Lemma 4.4, $\Gamma -S$ has exactly one such component. Denote the vertices of the singleton components by $w_1, \ldots , w_{|S|-3}$, and denote the remaining component by C. Let $s \ge 2$ denote the number of edges contained in S and let t be the number of edges between S and C. Then, counting the edges between S and $V(\Gamma ) {\setminus } S$ in two ways we get

$$\begin{aligned} k|S| - 2s = k(|S|-3) + t = k|S| + t -3k, \end{aligned}$$

(6)

and so $t+2s = 3k$. Since Lemma 4.3 implies that $t > 3k/2$, we thus get the inequality $s < 3k/4$. Since $N(w_1) \subseteq S$ and the number of edges contained in $N(w_1)$ is clearly $k \lambda /2$, we have that $k \lambda /2 < 3k/4$, and so $\lambda \in \{0,1\}$. Moreover, $|S| \ge k \ge 5$, so that there are at least two singleton components of $\Gamma - S$.

Pick $w_i, w_j$, where $1 \le i<j \le |S|-3$, and suppose $|N(w_i) \cap N(w_j)| = \mu _2$. As $\mu _2 < \mu _1 \le k$ there are thus $k - \mu _2 \ge 1$ vertices $w \in N(w_i) {\setminus } N(w_j)$. Each such w sends at least $\mu _2$ edges to $N(w_j)$, and so $s \ge (k-\mu _2)\mu _2$. However, it is easy to see that $(k-\mu _2)\mu _2 \le 3k/4$ implies $\mu _2 \in \{0,k\}$, which is impossible. Therefore, each pair $w_i$ and $w_j$, where $1 \le i < j \le |S|-3$, must have $\mu _1$ common neighbours. We now consider the two cases depending on whether $\lambda$ is 1 or 0 separately.

Case 1: $\lambda =1$.

Note that in this case the neighbours of a vertex come in (adjacent) pairs, so k is even, implying that $|S| \ge k \ge 6$. Now, since $s < 3k/4$, not all vertices of S have more than one neighbour in S, so let $u \in S$ have a unique neighbor in S, say v (recall that each vertex of S has a common neighbour with $w_1$ which is of course in S).

Since u has at least one common neighbour with each of $w_i$, $1 \le i \le |S|-3$, this neighbour must be v, and so $k = |N(v)| \ge |S|-2$. Observe that $|S|=k$ would contradict $\lambda = 1$, as then u and v would both be adjacent to all of $w_i$ (and $|S|-3 \ge 3$). On the other hand, $k = |S|-2$ would imply that u is the unique neighbour of v in S, and so u would also be adjacent to all of $w_i$, also contradicting $\lambda = 1$. Thus $k = |S|-1$. But since $|S|-3 \ge 3$, there exist at least two of the vertices $w_i$ which are both adjacent to $u_1$ and $v_1$ or are both adjacent to $u_2$ and $v_2$, again contradicting $\lambda = 1$.

Case 2: $\lambda =0$.

Since $w_1$ cannot be adjacent to both $u_1$ and $v_1$ nor to both $u_2$ and $v_2$, we must have $k \le |S| - 2$ and consequently $|S| \ge 7$. We first claim that $t \ge 2k$. Recall that, by Lemma 4.2, we have $|N(v) \cap S| \ge 2$ for each $v \in C$, and so $t \ge 2m$, where $m = |C|$. Our claim thus surely holds if $m \ge k$, so we can assume $k \ge m + 1$. Since there are no 3-cycles in C, the well-known result of Mantel (see [5, Theorem 7.1.1] for a more general Turán’s theorem) implies there are at most $(m^2-1)/4$ edges contained in C, and therefore $t \ge km - 2(m^2-1)/4$. Thus $k \ge m+1$ implies

$$\begin{aligned} t - 2k \ge k(m-2) - {m^2-1 \over 2} \ge (m+1)\frac{m-3}{2} \ge 0, \end{aligned}$$

and the claim follows. Observe that (6) now in fact implies $s \le k/2$.

This shows that there must exist a vertex $u \in S$ having no neighbours in S, since otherwise $k/2 \ge s \ge |S|/2$, contradicting the fact that $k \le |S|-2$. For the diameter of $\Gamma$ to be 2, the vertex u thus has to be adjacent to each $w_i$, $1 \le i \le |S|-3$, and to at least one vertex of C, implying that $k = |S| - 2$ and that u has a unique neighbour, say v, in C. But now $v \sim w$ for all $w \in C {\setminus } \{v\}$, while there are no other edges in C (recall that $\lambda = 0$), and so

$$\begin{aligned} t = k - (m-1) + (m-1)(k-1) = k + (m-1)(k-2). \end{aligned}$$

Thus (6) implies $2k = 2s + (m-1)(k-2)$, yielding $m = 3$ and $s = 2$.

Now, pick $w \in S {\setminus } \{u, u_1, v_1, u_2, v_2\}$ (recall that $|S| \ge 7$). As $\lambda = 0$, none of $w_i$, $1 \le i \le |S|-3$, is adjacent to both $u_1$ and $v_1$ nor to both $u_2$ and $v_2$, and so they are all adjacent to w. Similarly, both vertices from $C {\setminus } \{v\}$ have $|S|-3$ neighbours in S and since none of them is u, they must also be adjacent to w. But then w has at least $|S| - 1 > k$ neighbours, a contradiction. $\square$

5 Proof of the Main Theorem

In this section we finally prove Theorem 1.2. Let $\Gamma$ be as in Hypothesis 4.1. By Proposition 4.5, all components of $\Gamma - S$ are singletons. The corresponding vertices will be denoted by $w_1, w_2, \ldots , w_{|S|-2}$ for the rest of this paper. We first determine the parameters $\lambda$ and $\mu _2$ and determine the subgraph of $\Gamma$, induced on S.

Lemma 5.1

Under Hypothesis 4.1, we have $\lambda = 0$, $\mu _2 = 1$ and $|S| = 2k$. In addition, the subgraph of $\Gamma$, induced on S, is a disjoint union of k edges.

Proof

Let s denote the number of edges of the subgraph of $\Gamma$, induced on S. Counting the edges between S and $\Gamma - S$ in two ways we thus obtain

$$\begin{aligned} k|S| - 2s = k(|S|-2) = k|S| - 2k, \end{aligned}$$

implying that $s = k$.

Suppose now there exists a vertex $v \in S$ such that $N(v) \subseteq S$. Then the connected components of $\Gamma - S'$, where $S' = S {\setminus } \{v\}$, coincide with the ones of $\Gamma - S$, except for the new singleton component consisting of the vertex v. But then $o(\Gamma - S') = |S| - 1= |S'|$, and so Corollary 2.6 implies that $\Gamma$ is not 1-extendable (note that $S'$ contains at least one edge), contradicting Proposition 2.2. Thus each $v \in S$ has a neighbour in $\Gamma - S$. Now, if some $v \in S$ has no neighbours in S, then it must be adjacent to each $w_i$ (otherwise the diameter of $\Gamma$ would be at least 3), and so $k = |S| - 2$ and $\lambda = 0$ hold (as $w_1$ and v have no common neighbours). But as $s = k \ge 5$, there is then at least one adjacency between the $|S|-2$ neighbours of $w_1$, contradicting $\lambda = 0$. Thus each vertex of S has a neighbour in S as well as in $\Gamma - S$.

If each $u \in S$ has at least two neighbours in S then $k = s \ge |S| \ge k$, implying that $k = |S|$ (so that each $w_i$ is adjacent to entire S) and that each vertex of S has exactly two neighbours in S. But then $u_1$ and $v_1$ have at least $|S|-2 = k-2 \ge 3$ common neighbours, while any neighbour of $w_1$ can have at most two common neighbours with $w_1$ (as they all must be in S), contradicting the existence of the parameter $\lambda$. There thus exists some $u \in S$, having exactly one neighbour, say v, in S.

For any of the $k - 1 \ge 4$ neighbours $w_i$ of u in $\Gamma - S$ the only possible common neighbour of u and $w_i$ is v, showing that $\lambda \le 1$. In fact, if $\lambda = 1$, then u has a common neighbour with each $w_i$, implying that v must be adjacent to all of them, and so $k \ge |S|-2+1$, which then implies that u also is adjacent to each $w_i$ and consequently $k = |S|-1$. But then u and v have $k-1 \ge 4$ common neighbours, a contradiction, which shows that in fact $\lambda = 0$ holds.

Observe next that u cannot be adjacent to all of $w_i$, since then the fact that each vertex of S has a neighbour in $\Gamma - S$ would imply that u and v have a common neighbour, contradicting $\lambda = 0$. Thus $k \le |S|-2$, and so letting $w_i \in \Gamma - S$ be one of the nonneighbours of u, we then see that v is the only possible common neighbour of u and $w_i$, and so the fact that $\Gamma$ is of diameter 2 forces $\mu _2 = 1$.

Finally, since each of the $|S| - k$ nonneighbours of $w_1$ from S must have at least one common neighbour with $w_1$, we have $k = s \ge |S| - k$, and so $|S| \le 2k$. For each $1 \le i \le |S|-2$ each of the k vertices in $N(w_i)$ has a neighbour in S, which in fact has to be in $S {\setminus } N(w_i)$ (as $\lambda = 0$), giving rise to at least k edges in S. But then $s = k$ implies that each vertex of $N(w_i)$ has exactly one neighbour in S, and so the fact that each vertex of S is adjacent to at least one $w_i$, actually implies that each vertex of S has exactly one neighbour in S. Consequently $|S| = 2k$ and the induced subgraph on S is a disjoint union of k edges. $\square$

Proof of Theorem 1.2

That the four graphs from the theorem are indeed not 2-extendable and are quasi-strongly regular of diameter 2, follows from Theorems 3.1 and 3.3.

For the converse assume that $\Gamma$ is a quasi-strongly regular graph with parameters $(n, k, \lambda ; \mu _1, \mu _2)$ with n even and $\mu _1 > \mu _2 \ge 1$, which is not 2-extendable. If $k \le 4$, we can apply Theorems 3.1 and 3.3 (note that the only quasi-strongly regular graph with valency 2, diameter 2 and of even order is the 4-cycle $C_4$). We now show that k cannot be greater than 4.

Assume to the contrary that $k \ge 5$. By Proposition 2.3 the graph $\Gamma$ must be of grade 2. We can thus adopt Hypothesis 4.1. By Proposition 4.5, all components of $\Gamma -S$ are singletons (we denote the corresponding vertices by $w_i$, $1 \le i \le |S|-2$) and by Lemma 5.1 we have that $\lambda = 0$ and $\mu _2 = 1$, while the induced subgraph of $\Gamma$ on S is a disjoint union of k edges, implying that $|S| = 2k$.

Denote the vertices of S by $u_i, v_i$, where $1 \le i \le k$, in such a way that $v_i$ is the unique neighbour of $u_i$ in S. Since $\lambda =0$, we have that

$$\begin{aligned} N(u_i) \cap N(v_i) = \emptyset \quad \mathrm {and}\quad (N(u_i) \cup N(v_i)) {\setminus } \{u_i, v_i\} = V(\Gamma - S) \end{aligned}$$

(7)

holds for each $1 \le i \le k$. Moreover, every $w_j$, $1 \le j \le 2k-2$, is adjacent to exactly one of $u_i, v_i$ for each $1 \le i \le k$. Consider now $u_2$, which is of course at distance 2 from both $u_1$ and $v_1$. If $|N(u_2) \cap N(u_1)| = |N(u_2) \cap N(v_1)| = \mu _1$, then (7) implies that $k-1 = 2\mu _1$ is even and we have $\mu _1 = (k-1)/2$. By Proposition 2.7, it follows that $t_1 = 2(k-1)$, and so there exist $2(k-1)$ vertices, which have $\mu _1$ common neighbours with $w_1$. However, for each vertex x of S the vertex $w_1$ is either adjacent to x or has just one common neighbour with x, and so $2(k-1) = t_1 \le |S|-3 = 2k-3$, a contradiction.

It follows that one of the vertices $u_1$ and $v_1$ has a unique (recall that $\mu _2 = 1$) common neighbour with $u_2$, and so (7) implies that the other has $k-2 = \mu _1$ common neighbours with $u_2$. By Proposition 2.7, we have $t_1 = k-1$ and $t_2 = 2(k-1)$. Let $2 \le j \le 2k-2$ be such that $w_1$ and $w_j$ have just one common neighbour (note that $t_1 = k-1 < 2k-3$, so that j exists). Without loss of generality assume $j = 2$. This means that, with one exception, for each $1 \le i \le k$ one of $w_1$ and $w_2$ is adjacent to $u_i$ while the other is adjacent to $v_i$. With no loss of generality assume $w_1 \sim u_i$ for each $1 \le i \le k$, $w_2 \sim u_1$ and $w_2 \sim v_i$ for each $2 \le i \le k$. Now, since $w_1$ and $w_2$ have one common neighbour and each of $w_1$ and $w_2$ is adjacent to k vertices of S and has one common neighbour with each of the remaining k vertices of S, there are $t_2 - k - 1 = k - 3$ vertices $w_j$, $3 \le j \le 2k-2$, having one common neighbour with $w_1$, and there are $k-3$ vertices $w_{j'}$, $3 \le j' \le 2k-2$, having one common neighbour with $w_2$. As $k \ge 5$, these two sets of $k-3$ vertices are disjoint, and so there are $2k-4-2(k-3) = 2$ vertices, say $w_3$ and $w_4$, which have $\mu _1$ common neighbours with both $w_1$ and $w_2$. But by the above remarks this can only happen if both $w_3$ and $w_4$ are adjacent to $u_1$ and $1 + (k-1)/2 = \mu _1 = k-2$ holds, implying that $k = 5$.

With no loss of generality assume $w_3 \sim u_2, u_3, v_4, v_5$. Then each of these four vertices has at least two common neighbours with $u_1$ (namely $w_3$ and one of $w_1$ and $w_2$), and so these are the $t_1 = 4$ vertices having $\mu _1 = 3$ common neighbours with $u_1$. But as $w_4$ is the only remaining neighbour of $u_1$ (apart from $v_1, w_1, w_2$ and $w_3$), this implies that each of $u_2, u_3, v_4$ and $v_5$ is adjacent to $w_4$, implying that $w_3$ and $w_4$ have $5 > \mu _1$ common neighbours. This contradiction finally shows that $k \le 4$, as claimed. $\square$