A Characterization of Spartan Graphs and New Lower Bounds for Eternal Vertex Cover

Let $G$ be a non-elementary connected bipartite graph with $V(G)=A\cup B$, where $A$ and $B$ are non-empty independent sets, and a perfect matching. Suppose that for every non-empty subset $S$ of $A$, $S⊊A$ we have $|N(S)|>|S|$. Let $ab\in E(G)$. We show that there exists a perfect matching between $A\setminus \{a\}$ and $B\setminus \{b\}$. Consider any non-empty $X\subseteq A\setminus \{a\}$. If , then $|N(X)\cap B|\le |X|$. That is, $X⊊A$ such that $|N(X)|\le |X|$, which is contrary to our assumption that for every subset $S$ of $A$, $S⊊A$ we have $|N(S)|>|S|$. Thus, we cannot have any $X\subseteq A\setminus \{a\}$ such that . Therefore, by Hall’s theorem, there exists a perfect matching $M_1$ between $A\setminus \{a\}$ and $B\setminus \{b\}$. Thus, $M=M_1\cup \{ab\}$ is a perfect matching of $G$ containing $ab$. Since $ab$ was an arbitrary edge of $G$, every edge of $G$ belongs to some perfect matching, and $G$ is connected. This implies that $G$ is elementary which is a contradiction. Therefore, there must exist a non-empty subset $S$ of $A$ such that $S⊊A$ and $|N(S)|\le |S|$ but $|N(S)|$ cannot be less than $|S|$ because $G$ has a perfect matching. Thus $|N(S)|=|S|$. With a symmetric argument, we get that there exists a non-empty $T⊊B$ such that $|N(T)|=|T|$. $◀$

Consider a Spartan graph $G$ (with more than one vertex), and let $I$ be a maximum independent set of $G$ and $C=V(G)\setminus I$ be a minimum-sized vertex cover. Suppose there is no matching from $I$ to $S$ which saturates $I$, then by Hall’s theorem, there exists $X\subseteq I$ such that . (Here, the neighborhood of any subset of $I$ in the entire graph is the same as the neighborhood of that subset in $C$ because $I$ is an independent set.)

Consider an inclusion-wise minimal such subset $X$ of $I$. Then for every $x\in X$, there exists a perfect matching from $X\setminus \{x\}$ to $N(X)$. If not, then there exists a $Y\subseteq X\setminus \{x\}$ such that and as $Y\subseteq X\setminus \{x\}$ which means that $Y\subset X$, this contradicts the inclusion-wise minimality of $X$. Hence, there exists a perfect matching from $X\setminus \{x\}$ to $N(X)$ and this also means that $|X|=|N(X)|+1$. Next, we make a claim which demonstrates how any vertex cover of $G$ intersects the vertices in $X\cup N(X)$ and its proof is given in the Appendix.

Now consider a vertex $x\in X$. Since $G$ is Spartan, there is a minimum-sized vertex cover $S_x$ of $G$ such that $x\in S_x$ by Lemma 3. We have already shown that $X\setminus \{x\}$ has a perfect matching with $N(X)$. Thus, any vertex cover must contain $|N(X)|$ vertices from $X\setminus \{x\}\cup N(X)$. Thus, $S_x$ contains $x$ and $|N(X)|$ vertices from $X\setminus \{x\}\cup N(X)$. That is, $S_x$ contains $|N(X)|$ vertices from $X\cup N(X)$. This contradicts the above claim. Thus, the existence of a Hall’s violator set $X$ is not possible and there exists a matching from $I$ to $S=V(G)\setminus I$ which saturates $I$. $◀$ This immediately gives us a simple corollary (proof in Appendix).

When we are dealing with more than $\mathrm{𝗆𝗏𝖼}(G)$ guards, and we are in the model of the game where more than one guard is able to occupy a single vertex, then we will need to look at configurations of guards, not just vertex covers or vertex sets. A configuration of guards is a description of how many guards are present on each vertex of the graph $G$. A configuration can also be viewed as a function which maps each vertex to a non-negative integer such that the sum of the values of this function on all the vertices of $G$ is equal to the number of guards. At some places, we will also view a configuration as a multi-set where a vertex appears as many times as the number of guards present on it. The manner in which we are using the word configuration, will be clear from context. When we say a configuration of guards $𝒞$ on a vertex cover $S$, we mean that the vertices having one or more guards in $𝒞$ (i.e., a non-zero value for the configuration function) are precisely the ones in $S$.

If the number of guards on $G$ is the same as $\mathrm{𝗆𝗏𝖼}(G)$, or we are working in the model where only one guard per vertex is allowed, then the vertex cover formed by vertices occupied by the guards in a weakly good configuration is a weakly good vertex cover. It is easier to see the notion of a weakly good vertex cover (or configuration) by looking at a vertex cover (or configuration) which is not weakly good.

For every vertex cover $S$ which is not weakly good, there must exist at least one corresponding weakly bad set $T\subset V(G)\setminus S$. Similarly for every configuration $𝒞$ which is not weakly good, there must exist at least one corresponding weakly bad set $T\subset V(G)\setminus S$. Conversely, if for a vertex cover $S$ (or a configuration $𝒞$ occupying the vertices in a vertex cover $S$), there exists a subset $T$ of $V(G)\setminus S$ which is weakly bad, then the vertex cover $S$ (or the configuration $𝒞$) is not weakly good.

Suppose a graph $G$ has $\mathrm{𝖾𝗏𝖼}(G)=k$, and there exists $v\in V(G)$ such that there does not exist a weakly good configuration with $k$ guards with a guard on $v$. Without loss of generality, we can assume that the defender starts with a configuration with a guard on $v$, because the attacker can always attack an edge adjacent to $v$, and ensure that at least one guard comes to $v$. As there exists no weakly good configuration with $k$ guards, which has a guard on $v$, the configuration $𝒞$ formed by the guards cannot be a weakly good configuration. If the guards do not occupy a vertex cover, some edge must be vulnerable and the attacker can attack that edge. So, we can assume that the set $S$ of vertices occupied by the guards in the configuration $𝒞$ forms a vertex cover. Therefore, there exists a weakly bad subset $T$ of the unoccupied vertices such that if $C_1,C_2,\mathrm{\dots },C_{\mathrm{\ell }}$ are the connected components of $G[V(G)\setminus T]$, we must have a $C_i$ (where $i\in [1,\mathrm{\ell }]$), which contains $\mathrm{𝗆𝗏𝖼}(C_i)$ guards. Now, since the components are not adjacent to each other, there exists an edge from a vertex $w\in V(C_i)$ to a vertex $u\in T$ because the graph $G$ is connected. Since no vertex in $T$ has a guard, the guard on $w$ must come to $u$. Therefore, some edge in $C_i$ will become vulnerable, as there were only $\mathrm{𝗆𝗏𝖼}(C_i)$ many guards in $V(C_i)$, and one guard has moved out of $C_i$, while no guard from outside can come to a vertex of $C_i$ in one step. Thus, the attacker wins, and this contradicts $\mathrm{𝖾𝗏𝖼}(G)=k$. $◀$

Let $x$ be a cut vertex of a graph $G$, and let $S$ be a vertex cover of $G$ which does not contain $x$. Then we show that $\{x\}\subset V(G)\setminus S$ is weakly bad, which will imply that $S$ is not a weakly good vertex cover. Since $x$ is a cut vertex, there exist connected components $C_1,C_2,\mathrm{\dots },C_{\mathrm{\ell }}$ where $\mathrm{\ell }\ge 2$ of $V(G)\setminus \{x\}$. If $|S\cap V(C_i)|>\mathrm{𝗆𝗏𝖼}(C_i)$ for all $i\in [1,\mathrm{\ell }]$, then $S^{\prime }=\{x\}\cup S_1\cup S_2\cup \mathrm{\dots }\cup S_{\mathrm{\ell }}$ will be a vertex cover of $G$ of size $|S|-\mathrm{\ell }+1$ (where $S_i$ is a vertex cover of $C_i$ of size $\mathrm{𝗆𝗏𝖼}(C_i)$). This is not possible as and $S$ is a minimum-sized vertex cover of $G$. Thus, there exists some $i\in [1,\mathrm{\ell }]$ such that $|S\cap V(C_i)|=\mathrm{𝗆𝗏𝖼}(C_i)$, which implies that $\{x\}$ is a weakly bad set. Hence, $S$ is not a weakly good vertex cover. $◀$ Thus, with Lemma 12 and Lemma 13, we get the result in [2] that states that if $\mathrm{𝖾𝗏𝖼}(G)=\mathrm{𝗆𝗏𝖼}(G)$, then each vertex must belong to a minimum-sized vertex cover which contains all the cut vertices.

We next define a generalization of a bad set, which is used to define the notion of a strongly good vertex cover. We use this notion to give another necessary condition for a graph $G$ to be Spartan. In order to define this, we define the notion of compatible vertex sets (or vertex covers) in a graph. We also give analogous definitions of compatible configurations and strongly good configurations. This gives us a new lower bound for $\mathrm{𝖾𝗏𝖼}(G)$.

Also, when we say ${𝒞}_i\setminus {𝒞}_j$, we account for multiplicity of each vertex. That is, if $v$ occurs $5$ times in ${𝒞}_1$ and $3$ times in ${𝒞}_2$, $v$ will occur $2$ times in ${𝒞}_1\setminus {𝒞}_2$. Also, when we say vertex-disjoint paths (counting multiplicity) between ${𝒞}_1\setminus {𝒞}_2$ and ${𝒞}_2\setminus {𝒞}_1$, we mean that if a vertex $v$ occurs multiple times in ${𝒞}_1\setminus {𝒞}_2$, each occurrence of $v$ will be an endpoint of exactly one path from ${𝒞}_1\setminus {𝒞}_2$. Similarly, if a vertex $v$ occurs multiple times in ${𝒞}_2\setminus {𝒞}_1$, each occurrence of $v$ will be an endpoint of exactly one path to ${𝒞}_2\setminus {𝒞}_1$. If we consider the union of all the multisets formed by the intermediate vertices (i.e., the vertices of ${𝒞}_1\cap {𝒞}_2$) of each path, the number of times a vertex $v$ occurs in the union, should be less than or equal to the number of times $v$ occurs in ${𝒞}_1\cap {𝒞}_2$.

It is clear that two configurations ${𝒞}_1$ and ${𝒞}_2$ are compatible, if and only if there is a possible movement of guards from ${𝒞}_1$ to ${𝒞}_2$, where each guard moves at most one step. The guards can rearrange themselves by moving one step from ${𝒞}_1\setminus {𝒞}_2$ to ${𝒞}_2\setminus {𝒞}_1$ if and only if there exist $|{𝒞}_1\cap {𝒞}_2|-$many vertex disjoint paths (counting multiplicity) between ${𝒞}_1\setminus {𝒞}_2$ and ${𝒞}_2\setminus {𝒞}_1$. For more explanation on the equivalence between the guard movements and vertex-disjoint paths, please refer to Figure 2.

The following is a known result shown in [2].

Now we analogously define a strongly good configuration.

Now we make an observation which relates the notions of weakly good and strongly good configurations (vertex covers).

We prove the contrapositive of this statement, i.e., a configuration on a vertex cover which is not a weakly good configuration, is also not a strongly good configuration. Let $𝒞$ be a configuration on a vertex cover $S$, such that $𝒞$ is not weakly good. Therefore, there exists a non-empty $T\subseteq I=V(G)\setminus S$, such that if $C_1,C_2,\mathrm{\dots },C_{\mathrm{\ell }}$ are the connected components of $G[V(G)\setminus T]$, there must exist a $C_i$ (where $i\in [1,\mathrm{\ell }]$) such that the number of guards in $C_i$ (in $𝒞$) is equal to $\mathrm{𝗆𝗏𝖼}(C_i)$. Since $T$ is non-empty and the graph $G$ is connected, there exists $v\in V(C_i)$ such that $v$ is adjacent to $T$ and since $S$ is a vertex cover $v$ is in $S$ (and has exactly one guard in $𝒞$ as the number of guards in $C_i$ (in $𝒞$) is equal to $\mathrm{𝗆𝗏𝖼}(C_i)$). The configuration $𝒞\cap C_i\setminus \{v\}$ is not compatible with any vertex cover of $C_i$, as the number of guards in $𝒞\cap C_i\setminus \{v\}$ is less than $\mathrm{𝗆𝗏𝖼}(C_i)$. Thus the set $T$ is a strongly bad set, and $𝒞$ is not a strongly good configuration.

The same proof works for vertex covers, if we consider a vertex cover as a configuration with one guard per vertex. $◀$

Suppose that there exists a graph $G$ with $\mathrm{𝖾𝗏𝖼}(G)=k$ and a vertex $v$, such that there exists no $k-$sized strongly good configuration on a vertex cover containing $v$. Without loss of generality, we can assume that the initial configuration has at least one guard on $v$, because if not, the attacker can force a guard to come to $v$ by attacking an edge adjacent to $v$. If the vertices occupied by the guards in the resulting configuration do not form a vertex cover, then there exists some edge which is vulnerable, and hence the attacker wins. Therefore, the resulting configuration must have guards on a vertex cover. Since there is no $k-$sized strongly good configuration ${𝒞}_v$ on a vertex cover $S_v$ such that $v\in S_v$, for the configuration $𝒞$ formed by the guards on the vertex cover $S$, there exists a strongly bad subset $T\subset V(G)\setminus S$. Hence, there is some connected component $C_i$ of $V(G)\setminus T$ and some $u\in N(T)\cap V(C_i)$ such that no configuration on a vertex cover of $C_i$ of size $𝒞\cap V(C_i)-1$ is compatible with $S\cap V(C_i)\setminus \{u\}$. Suppose the attacker attacks an edge joining $u$ to a vertex in $T$, the guard on $u$ is forced to move to $T$. No guard from a vertex outside $C_i$ can come to $C_i$ and the guards in $C_i$ cannot rearrange themselves to form a vertex cover of $C_i$. Therefore, some edge will be vulnerable no matter how the guards rearrange themselves, which contradicts $\mathrm{𝖾𝗏𝖼}(G)=k$.

Therefore, a graph $G$ has $\mathrm{𝖾𝗏𝖼}(G)=k$, only if for each $v\in V(G)$, there exists a $k-$sized strongly good configuration ${𝒞}_v$ on a vertex cover $S_v$ where $v\in S_v$. $◀$

As described in Lemma 4, it suffices to look at connected graphs i.e., it will be sufficient to prove that a connected König-Egerváry graph $G$ is Spartan if and only if it is bipartite and elementary. The reverse direction has already been proved in [1]. Thus we need to only show that if a connected König-Egerváry graph $G$ is Spartan, then it is bipartite and elementary.

Since $G$ is Spartan, let $S$ be a minimum-sized vertex cover of $G$, which is an eternal vertex cover configuration, and let $I=V(G)\setminus S$ be the corresponding independent set. By Lemma 5, there exists a matching $M$ from $I$ to $S$, which saturates $I$. This means that $|S|\ge |I|$. Since $S$ is a minimum-sized vertex cover, each edge of any matching, and hence a maximum matching of $G$ must have at least one endpoint in $S$. Suppose some edge of a maximum matching has two endpoints in $S$, then $|S|>mm(G)$, which contradicts the assumption that $G$ is a König-Egerváry graph. Therefore, every edge of a maximum matching of $G$ has exactly one endpoint in $S$. Thus, $|S|\le |V(G)\setminus S|$ i.e., $|S|\le |I|$. Hence we obtain $|S|=|I|=V\left(G\right)/2$, and $M$ is a perfect matching of $G$.

Now, consider the bipartite graph $H$ with $V(H)=V(G)$, and $E(H)=E(G)\setminus E(G[S])$. That is, $H$ has the same vertex set as that of $G$, and the edge set of $H$ consists of edges of $G$ going across from $S$ to $I$. Now $V(H)=S\cup I$, such that $S$ and $I$ are independent sets in $H$, and $M$ is a perfect matching of $H$. Suppose there exists $T⊊I$, such that $|N(T)|=|T|$ in $H$. Since $I$ is an independent set in $G$ as well, we have $|N(T)|=|T|$ in $G$. Since $T⊊I$, $T$ is an independent set of $G$ which is not maximal. Thus, by Corollary 23, we get that $G$ is not Spartan, which is a contradiction. Therefore, $H$ must be elementary, by Lemma 2.

Thus, we know that $H$ can have only the two minimum-sized vertex covers $S$ and $I$ (using an alternate definition of elementary bipartite graph from [5]). Since $E(H)\subseteq E(G)$, any vertex cover of $G$ must be a vertex cover of $H$. Thus, $G$ cannot have any minimum-sized vertex cover other than $S$ and $I$. If there is an edge of $G$ with both its endpoints in $S$, then $I$ is not a vertex cover of $G$ and thus $S$ is the only minimum-sized vertex cover of $G$. For $v\in I$, there does not exist a minimum-sized vertex cover of $G$ which contains $v$. Thus, using Lemma 3, we get that $G$ is not Spartan, which is a contradiction. Thus, there cannot be any edge with both the endpoints in $S$. Thus, $E(G)=E(H)$ and we already know that $V(G)=V(H)$ and $H$ is bipartite and elementary. Therefore, $G$ is bipartite and elementary. $◀$

Since $S\setminus T$ and $T\setminus S$ are subsets of independent sets $V(G)\setminus T$ and $V(G)\setminus S$ respectively, the graph ${𝔥}_G(S,T)$ is bipartite. $◀$

First, assume that $G$ is Spartan. Then, there is a strategy for indefinite defense of $G$ with $\mathrm{𝗆𝗏𝖼}(G)$ guards. Let $ℱ$ be the set of all vertex covers that are used in the strategy: note that they are all of minimum size by definition. Since $G$ is Spartan, $ℱ$ is indeed non-empty.

Consider a vertex cover $S\in ℱ$ and an edge $uv$ such that $u\in S$ and $v\notin S$.

As $S$ occurs in the strategy of the defender, there is a way to defend an attack on an edge when guards occupy the vertices of $S$ (one guard on each vertex). We attack the edge $uv$ here and observe the promised defense: let us say that the guards are positioned on the vertex cover $T$ after the defense is executed. Clearly, $T\in ℱ$, by definition. Depending on whether $u\in T$ or not, we can conclude that either (1) holds or (2) does (respectively), by tracing the movement of the guards from vertices in $S\setminus T$ to vertices in $T\setminus S$.

Suppose $u\notin T$, we show that (1) holds. Let $S^{\prime }=S\setminus T$, i.e., the set of vertices which had a guard before the attack and do not have a guard after the defense is completed. Let $T^{\prime }=T\setminus S$, i.e., the set of vertices which had a guard after the defense is completed and do not have a guard before the attack. Let $|S^{\prime }|=|T^{\prime }|=k$. Then there must be a collection $𝒫$ of $k$ vertex disjoint paths from $S^{\prime }$ to $T^{\prime }$ (with the starting vertex of each path from $S^{\prime }$, end vertex in $T^{\prime }$, and each intermediate vertex from $S\cap T$), and one of these paths must be the edge $uv$. We show how the collection $𝒫$ is obtained. Each path is obtained by tracing the movement of each individual guard. The guard on $u$ is forced to move to $v$ by the attacker and hence the edge $uv$ is traced by a guard. Thus $uv\in 𝒫$. Similarly look at the movement of a guard on a vertex say $u_1\ne u$ of $S^{\prime }$. This guard moves to some vertex $u_2$. If $u_2\in T$, $u_1{u}_2\in 𝒫$. Otherwise $u_2\in S\cap T$ as the guard can only move for one step after each attack and hence $u_2$ must have a guard both before and after the attack. The guard which previously was on $u_2$ moves to some $u_3$ (as both $S$ and $T$ are vertex covers hence there must be only one guard per vertex after the reconfiguration has been done). Now again if $u_3\in T$, $u_1{u}_2{u}_3\in 𝒫$. Otherwise $u_3\in S\cap T$ and the guard which was previously on $u_3$ must move to some $u_4$. This process will only stop when a guard moves to a vertex which did not already have a guard, i.e., a vertex in $T^{\prime }$. We obtain $k$ paths by tracing the movement of each of the $k$ guards in $S^{\prime }$ (including the guard moving from $u$ to $v$). It is clear that a vertex $v$ in $S^{\prime }$ or $T^{\prime }$ cannot belong to two paths because this will indicate that two guards started from the vertex $v$ (if $v\in S^{\prime }$) or two guards ended up at $v$ (if $v\in T^{\prime }$). A vertex $v\in S\cap T$ cannot belong to two paths in $𝒫$, because this will indicate that this vertex has at least two guards after the reconfiguration is done which is not possible. Also, each path in $𝒫$ which contains more than one edge must have all the intermediate vertices from the same connected component of $S\cap T$. This is because the intermediate vertices contain a guard both before and after the reconfiguration and hence lie in $S\cap T$. Each guard can move only to a neighboring vertex, the intermediate vertices of a path in $𝒫$ also form a path in $S\cap T$. Thus a path $u_1{u}_2\mathrm{\dots }{u}_t\in 𝒫$ where $t>2$ implies $u_1\in S^{\prime }$, $u_t\in T^{\prime }$ and $u_2,u_3,\mathrm{\dots },u_{t-1}\in V(H_i)$, for some $i$. Therefore, in the graph ${𝔥}_G(S,T)$, there exists a helper edge of color $i$ between $u_1$ and $u_t$. Also an edge in $𝒫$ corresponds to a real edge in ${𝔥}_G(S,T)$. Thus, each path in $𝒫$ gives an edge in ${𝔥}_G(S,T)$. The edges in ${𝔥}_G(S,T)$ corresponding to the paths in $𝒫$ form a perfect matching, because each vertex in $S^{\prime }$ is adjacent to exactly one edge corresponding to a path in $𝒫$. This is because there is only one guard on each vertex of $S^{\prime }$ before the attack and each vertex in $S^{\prime }$ has no guard after the attack. Thus, ${𝔥}_G(S,T)$ contains a perfect matching containing the edge $uv$ and condition (1) holds.

Now suppose $u\in T$, we show that (2) holds. Let $S^{\prime }$ and $T^{\prime }$ be the same as above, and similarly $k=|S^{\prime }|=|T^{\prime }|$. By the same reasoning as the previous case, we have $k$ vertex disjoint paths in $G$, which correspond to a perfect matching $M$ in ${𝔥}_G(S,T)$. Now as $u\in S$ and $u\in T$, a guard is present on $u$ before the attack and after the reconfiguration is complete. Since $T$ is obtained from $S$ by applying the winning strategy for a defense after the attacker attacks the edge $uv$, the guard on $u$ must move to $v$ while reconfiguring from $S$ to $T$. Since a guard is present on $u$ after the attack, there must exist a path $u_1{u}_2\mathrm{\dots }{u}_t$ in $𝒫$, where $t>2$, such that $u_1\in S^{\prime }$, $u_{t-1}=u$ and $u_t=v$. Also, $u_2,u_3,\mathrm{\dots },u_{t-1}$ belong to the same connected component of $H_i$. This path corresponds to the following movement: A guard on a vertex $u_1$ of $S^{\prime }$ moves to a vertex $u_2$ of $S\cap T$. The guard on $u_2$ moves to $u_3$ of $S\cap T$, and so on, till the guard on $u_{t-2}$ moves to $u$, and the guard on $u$ moves to $v$. Clearly, the vertices $u_2,u_3,\mathrm{\dots },u_{t-1}$ must belong to the same connected component of $S\cap T$, because a guard can only move to a neighboring vertex. The edge $u_{1}v$ is a helper edge in ${𝔥}_G(S,T)$ and lies in $M$. The vertex $u_1$ has a neighbor $u_2$ in the connected component of $G[S\cap T]$ that contains $u$ (because there is a path $u_2{u}_3\mathrm{\dots }{u}_{t-1}=u$ in $G[S\cap T]$). Hence, (2) holds.

Thus, we have shown that when $G$ is Spartan, the family $ℱ$ of all vertex covers used in a strategy of the defender; satisfies the condition in Theorem 26.

Now we show the converse, i.e., if a graph $G$ has a family of minimum-sized vertex covers $ℱ$ which satisfy the condition in Theorem 26, then $G$ is Spartan. For this, we show that if the guards occupy a vertex cover $S\in ℱ$ and an arbitrary edge $uv$ is attacked, the guards can reconfigure themselves, such that at least one guard moves across the attacked edge $uv$, and the final positions of the guards form a vertex cover $T\in ℱ$.

Since $S$ is a vertex cover, there cannot be any edge with both the endpoints outside $S$. If an edge $uv$ such that $u,v\in S$ is attacked, the guard on $u$ moves to $v$, and the guard on $v$ moves to $u$. The attack is defended and the configuration $S$ is restored. Therefore, we need to consider the attack on an edge $uv$ such that $u\in S$ and $v\notin S$.

By the given condition, there exists a vertex cover $T\in ℱ$ such that and $v\in T$ such that:

1. (1)

   either $u\notin T$ and there is a perfect matching in ${𝔥}_G(S,T)$ which contains the edge $uv$,

2. (2)

   or $u\in T$, and there is a perfect matching in ${𝔥}_G(S,T)$, where the matched partner of $v$, say $w$, has a neighbor – in $G$ – among the vertices of $X$, where $X$ is the connected component of $G[S\cap T]$ that contains $u$.

Suppose (1) holds. We show that it is possible to reconfigure the guards from $S$ to $T$ such that one guard moves across $uv$. Let $S^{\prime }=S\setminus T$, $T^{\prime }=T\setminus S$ and $|S^{\prime }|=|T^{\prime }|=k$. It is enough to show that there is a collection $𝒫$ containing $uv$ of $k$ vertex disjoint paths from $S^{\prime }$ to $T^{\prime }$ with all the intermediate vertices in $S\cap T$. A path $u_1{u}_2\mathrm{\dots }{u}_t$ in $G$ where $u_1\in S^{\prime }$, $u_t\in T^{\prime }$ and $u_2,u_3,\mathrm{\dots },u_{t-1}\in S\cap T$ will represent the movement of a guard from $u_1$ to $u_2$, the movement of the guard previously on $u_2$ to $u_3$, and so on up to the movement of the guard previously on $u_{t-1}$ to $u_t$.

If there exists a perfect matching $M$ in ${𝔥}_G(S,T)$ such that it consists of possibly some real edges and at most one helper edge of each color, then there exists a collection $𝒫$ of $k$ vertex disjoint paths from $S^{\prime }$ to $T^{\prime }$ with intermediate vertices in each path from $S\cap T$. We show that a path in $𝒫$ can be obtained from each edge of $M$. A real edge in ${𝔥}_G(S,T)$ is also an edge in $G$. Thus, for each real edge $e$ in $M$, add $e$ to $𝒫$. A helper edge $uv$ of color $i$ implies the existence of a path $u_1(=u)u_2{u}_3\mathrm{\dots }{u}_t(=v)$ in $G$ where $t>1$ and $u_2,u_3,\mathrm{\dots },u_{t-1}\in V(H_i)$, where $H_i$ is a connected component of $S\cap T$. For each helper edge $e=wz$ in $M$ of color $i$, add a path $u_1(=w)u_2{u}_3\mathrm{\dots }{u}_t(=z)$ in $G$ where $t>1$ and $u_2,u_3,\mathrm{\dots },u_{t-1}\in V(H_i)$ to $𝒫$. Clearly, there are $k$ paths in $𝒫$ (one path obtained from each edge of $M$). We show that the paths in $𝒫$ are vertex disjoint. Since $M$ is a matching, the endpoints of each edge in $M$ are distinct. Hence the endpoints of all the $k$ paths are distinct. Since all the intermediate vertices of each path are distinct and each path of length at least $2$ is obtained from a helper edge of different color (as there are no two helper edges of the same color in $M$), each path obtained from a helper edge in $M$ has intermediate vertices from distinct components of $G[S\cap T]$. Thus all the intermediate vertices of each path in $𝒫$ are disjoint.

Now we show that there exists a perfect matching in ${𝔥}_G[S,T]$ which contains possibly some real edges and at most one helper edge of each color. By Lemma 16, there exists a perfect matching from $S^{\prime }$ to $T^{\prime }$ in $G$. This means that there exists a perfect matching $M_p$ in ${𝔥}_G(S,T)$ which consists of only real edges. Let $M$ be the perfect matching in ${𝔥}_G(S,T)$ such that $M$ contains $uv$ (exists by condition (1)), and the size of $M\cap M_p$ is as large as possible. Now, consider the graph $H$ in ${𝔥}_G(S,T)$ such that $V(H)=V({𝔥}_G(S,T))$ and $E(H)=M\cup M_p$. Since $M$ and $M_p$ are both perfect matchings, $H$ is a union of edges and even cycles.

If there are two distinct cycles $C_1$ and $C_2$ in $H$, at most one of them can contain the edge $uv$. Therefore, without loss of generality, we can assume that $uv\notin E(C_1)$. Suppose $C_1$ is a cycle and $C_1=u_1{v}_1{u}_2{v}_2\mathrm{\dots }{u}_t{v}_t{u}_1$, where $M_1:=\{u_1{v}_1,u_2{v}_2,\mathrm{\dots },u_t{v}_t\}\subset M$ and $M_2:=\{v_1{u}_2,v_2{u}_3,\mathrm{\dots },v_{t-1}{u}_t,v_t{u}_1\}\subset M_p$ with $t>1$. The matching $M^{\prime }:=M\setminus M_1\cup M_2$ has strictly more intersection with $M_p$ than $M$, and also contains the edge $uv$, which is a contradiction. $\mathrm{⊲}$ If $H$ has no cycle, then $M=M_p$, which means that all the edges of $M$ are real, and we are done. Now, we consider the case where $M$ has exactly one even cycle $C$. If $uv\notin E(C)$, then we get a contradiction by the same argument as the claim above. Therefore, let $C=u_1(=u)v_1(=v)u_2{v}_2\mathrm{\dots }{u}_t{v}_t{u}_1$. Here $M_1:=\{u_1{v}_1,u_2{v}_2,\mathrm{\dots },u_t{v}_t\}\subset M$ and $M_2:=\{v_1{u}_2,v_2{u}_3,\mathrm{\dots },v_{t-1}{u}_t,v_t{u}_1\}\subset M_p$. Also, $\{u_1,u_2,\mathrm{\dots },u_t\}\subset S^{\prime }$ and $\{v_1,v_2,\mathrm{\dots },v_t\}\subset T^{\prime }$. This is because $u\in S^{\prime }$ and ${𝔥}_G(S,T)$ is bipartite (by Lemma 25). All the edges in $M$ which are not in $M_1$, are also the edges of $M_p$, and hence are real. Next, we show that $M$ cannot contain two (or more) helper edges of the same color.

Suppose $M$ contains two helper edges of the same color (say $i$). These two edges must lie in $M_1$, because the edges of $M$ outside $M_1$ are real. Let these two edges be $u_p{v}_p$ and $u_q{v}_q$, where . (As $uv$ is a real edge, we have $p\ne 1$.) Therefore, there must exist edge $u_p{v}_q$ of color $i$. This is because $u_p$ and $v_p$ are both adjacent to some vertex in $V(H_i)$, and similarly $u_q$ and $v_q$ are both adjacent to some vertex in $V(H_i)$. Hence, $u_p$ and $v_q$ are adjacent to some vertex in $V(H_i)$. Also, $M_3:=\{v_p{u}_{p+1},v_{p+1}{u}_{p+2},\mathrm{\dots },v_{q-1}{u}_q\}\subset M_p$, hence the edges in $M_3$ are real edges of ${𝔥}_G(S,T)$. Let $M_4=\{u_p{v}_p,u_{p+1}{v}_{p+1},\mathrm{\dots },u_q{v}_q\}$ and $M_5=(M_1\setminus M_4)\cup M_3\cup \{u_p{v}_q\}$. Consider the perfect matching $M^{\prime }=(M\setminus M_1)\cup M_5$. It can be checked that $M^{\prime }$ is a perfect matching which contains $uv$, and has greater intersection with $M_p$ than $M$, which is a contradiction. $\mathrm{⊲}$

Thus, we have shown the existence of a perfect matching between $S^{\prime }$ and $T^{\prime }$ containing the edge $uv$ in ${𝔥}_G(S,T)$, which contains at most one helper edge of each color. This implies that there is a collection of $|S^{\prime }|$ vertex-disjoint paths from $S^{\prime }$ to $T^{\prime }$, such that one path in this collection is the edge $uv$. Therefore, the guards can reconfigure from $S$ to $T$ (such that one guard moves across $uv$).

Now, suppose (2) holds. Since $w$ has a neighbor in the same connected component $X=C_i$ (say) of $G[S\cap T]$ that contains $u$, this means that there exists a path $(w=)u_1{u}_2\mathrm{\dots }{u}_{t-1}(=u)u_t(=v)$, where $t>1$, such that $u_2,u_3,\mathrm{\dots },u_{t-1}(=u)$ belong to $V(C_i)$, that is, $wv$ is a helper edge of color $i$ in ${𝔥}_G(S,T)$. As we have seen above, a matching in ${𝔥}_G(S,T)$, with at most one helper edge of each color, can be used to show the existence of $|S\setminus T|$ vertex-disjoint paths from $S^{\prime }=S\setminus T$ to $T^{\prime }=T\setminus S$, with the intermediate vertices from $S\cap T$. This shows that, it is possible to reconfigure the guards from $S$ to $T$.