Pairs of disjoint matchings and related classes of graphs

Clearly, $\lambda(\hat{G})>\lambda(G)$ if and only if $(u,v)\in\hat{H}\cup\hat{H}^{\prime}$ for any $(\hat{H},\hat{H}^{\prime})\in\Lambda(\hat{G})$. The restriction of $(\hat{H},\hat{H}^{\prime})$ to $E$ gives a pair in $\Lambda(G)$ with $u,v$ unsaturated in $H$ or $H^{\prime}$. Conversely, if there is $(H,H^{\prime})\in\Lambda(G)$ such that, say, $H$ doesn’t saturate $u$ and $v$, then $(H\cup\{(u,v)\},H^{\prime})\in\Lambda(\hat{G})$. ∎

At most two of the edges incident to a central vertex can be in $H\cup H^{\prime}$. Thus, $H\cup H^{\prime}$ must leave out the inner edge of all except perhaps two legs adjoined to each central vertex. The maximality of $|H\cup H^{\prime}|$ requires that we include exactly two edges incident to each central vertex in $H\cup H^{\prime}$. The outer edges of the legs whose inner edges were left out must be in $H$ because otherwise, adding each such an edge to $H$ and removing it from $H^{\prime}$ if it was in $H^{\prime}$ results either in an increase of $H$ while preserving $|H\cup H^{\prime}|$ or in an increase of $|H\cup H^{\prime}|$. ∎

We take all the edges adjacent to the leaves and the unique edge between the central vertices. This is clearly a perfect matching and it contains one edge per leg, as well as another edge connecting the central vertices, so a total of $4+k+1$ edges. Fig. 2(a) illustrates this perfect matching in a $2$-spanner.

To verify the uniqueness of this perfect matching, note that the edges incident to the leaves have to be in any perfect matching, therefore the edges adjacent to them cannot be. This leaves only the edge between the two central vertices, so it has to belong to every perfect matching in order to saturate the central vertices.

Fix $(H,H^{\prime})\in\Lambda_{\mu}(G)$. By Lemma 3.2, the inner edges of all but two legs incident to each central vertex do not belong to $H\cup H^{\prime}$ and the outer edges of those legs are in $H$. Removing these legs from the graph results in a $0$-spanner, for which it’s easy to see that the maximum number of edges from $H\cup H^{\prime}$ is $8$, where $H$ has $4$ edges, and the only possibility is to leave the edge between the central vertices out. Each additional leg adds one edge to $H$ and none to $H^{\prime}$, so the formulas follow. For example, Fig. 5 illustrates a pair $(H,H^{\prime})$ in a $5$-spanner. ∎

Fix $(H,H^{\prime})\in\Lambda(G^{\prime})$ and note that it is enough to show that $v_{1}v_{2}\notin H\cup H^{\prime}$. Assume towards a contradiction that $v_{1}v_{2}\in H\cup H^{\prime}$. Then $(H\cap E_{i},H^{\prime}\cap E_{i})\notin\Lambda(G_{i})$ for each $i=1,2$ because $v_{i}$ is unsaturated with either $H\cap E_{i}$ or $H^{\prime}\cap E_{i}$. Thus, $\lambda(G)=|H\cup H^{\prime}|\leq 1+(\lambda(G_{1})-1)+(\lambda(G_{2})-1)=\lambda(G_{1})+\lambda(G_{2})-1$. But this contradicts the fact that for any $(H_{i},H_{i}^{\prime})\in\Lambda(G_{i})$, $(H_{1}\cup H_{2},H_{1}^{\prime}\cup H_{2}^{\prime})$ is a pair of disjoint matchings in $G^{\prime}$ with total number of edges equal $\lambda(G_{1})+\lambda(G_{2})$. ∎

By Corollary 3.3, the central vertices of every $S_{k}$ are saturated with both $H_{k}$ and $H_{k}^{\prime}$ for any $(H_{k},H_{k}^{\prime})\in\Lambda(S_{k})$. The statement, therefore, follows from Lemma 3.5. ∎

Note first that $n\geq m+1$ and $5m-4n\geq 0$. Let $G\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=G_{n-m}$ be a graph constructed as in Lemma 3.6, where we take a $0$-spanner as $S_{1},\dots,S_{n-m-1}$ and $k$-spanner as $S_{n-m}$. Then, by Lemmas 3.4 and 3.6 we get that $\mu(G)=4(n-m-1)+4+k=4n-4m+k$ and $\nu(G)=5(n-m-1)+5+k=5n-5m+k$, so taking $k\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=5m-4n$ makes $\mu(G)=m$ and $\nu(G)=n$. ∎

The hypothesis implies that $\lambda(G)\geq n-1$, i.e., $\lambda(G)$ is $n-1$ or $n$. Either way, $\mu(G)\geq{\lceil\frac{n-1}{2}\rceil}={\lfloor\frac{n}{2}\rfloor}$, so $\mu(G)=\nu(G)$ by Observation 4.1. ∎

A Hamiltonian path has $n-1$ edges, which lie in a pair of disjoint matchings, so Lemma 4.2 applies. ∎

(i): Suppose $P$ is a cycle. If $P$ is an odd cycle then note that two adjacent edges will be in the same matching, contradicting matching definition. Suppose then that $P$ is an even cycle. Consider $M^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(M\backslash P)\cup(H\cap P)$, and note that this is a matching since $P$ is an even cycle and maximum since $M$ is. Then $|M^{\prime}\cap(H\cup H^{\prime})|\geq|M\cap(H\cup H^{\prime})|$ and $|M^{\prime}\cap H|>|M\cap H|$, a contradiction.

(ii): By (i), $P$ is not a cycle, so $P$ is a path. Suppose that some end edge of $P$, $e_{0}$ is in $H$. $e_{0}$ can be incident to $M$ on only one side, as $P$ is a maximal alternating path. Call this $M\setminus H$ edge $e_{1}$. Since $e_{0}$ is incident to $M$ on only one side, we may define $M^{\prime}=(M\backslash\{e_{1}\})\cup\{e_{0}\}$. $M^{\prime}$ is a maximal matching, but $|M^{\prime}\cap H|>|M\cap H|$, contradicting that ($M,H,H^{\prime}$) was a maximal intersection triple. $P$ thus has no end edges in $H$. This implies that $P$ also has odd length.

(iii): Consider an end edge $e_{0}$ in $M\backslash H$. Again note that $e_{0}$ can be incident to $H$ on only one side. If $e_{0}$ is not in $H^{\prime}$, then we can remove $e_{1}$, the preceding edge, from $H$, add $e_{0}$ to $H$, and again increase $|M\cap(H\cup H^{\prime})|$.

(iv): Suppose instead some interior vertex is not incident to $H^{\prime}$, and note that this vertex is incident to no end edges. This vertex is incident to exactly one edge in $M$, which we call $e_{M}$. $e_{M}$ is incident to $H^{\prime}$ at most once. Via a similar argument to above, if we take $e_{M}$ to be in $H^{\prime}$ instead of this adjacent edge, we increase $|M\cap(H\cup H^{\prime})|$.

(v): Suppose towards a contradiction that all $M$ edges in $P$ are also in $H^{\prime}$. Swapping $H$ and $H^{\prime}$ on the path will increase $|M\cap H|$ and keep $|M\cap(H\cup H^{\prime})|$ the same, a contradiction. We are allowed to do this because the two end edges of $P$ are not connected to $H$.

(vi): Suppose there exists such a $C$. Observe that $C$ must contain some $M\backslash(H\cup H^{\prime})$ edge. To see this, note that because $P$ is acyclic, some $C\cap P\cap M$ edge, say $e$, is incident to fewer than two $C\cap P\cap H$ edges. Then $e$ must be adjacent to a $C\cap H^{\prime}$ edge, or else $P$ is not maximal. Then $e\notin H^{\prime}$, and $e\notin H$ since $e\in P$. Now, define $M^{\prime}\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=(M\backslash C)\cup(C\backslash M)$. $M^{\prime}$ is a matching since no vertex of $C$ is adjacent to an $M$ edge not already in $C$. $M^{\prime}$ is maximal since $M$ is. Because $C$ contained some $M\backslash(H\cup H^{\prime})$ edge, immediately $|M^{\prime}\cap(H\cup H^{\prime})|>|M\cap(H\cup H^{\prime})|$. ∎

The setup is depicted in Fig. 10. We will show that each piece of $P\setminus e$ must witness a chain of diamonds that terminates in a spanner-end. Observe first that $e$ is not an end edge of $P$ by (iii) of Lemma 4.9. Consider the right vertex $v$ of $e$. By (iv) of Lemma 4.9, it must be adjacent to an $H^{\prime}$ edge. By assumption, this edge does not cross over to the left side of $e$. Either this $H^{\prime}$ edge connects $v$ to some vertex not in $P$ or to another $P$ vertex to the right of $e$. In the first case, note that this $H^{\prime}$ edge must be connected to an $M$ edge, or else $|M\cap(H\cup H^{\prime})|$ is not maximal. This $M$ edge must also be off of $P$ since all $P$ edges are saturated with $M$. We now have a path of length at least 2 extending off of $P$, and we see that the right side of $e$ is now a “spanner-end”, as in Fig. 11.

If instead our $H^{\prime}$ edge connects back to the right of $v$ on $P$, then if it connects to a vertex of distance more than 2 away then we again have a spanner end, as shown in Fig. 12.

If instead it connects to the vertex 2 to the right of $v$, then if follows from (iv) of Lemma 4.9 that the vertex directly to the right of $v$ must also be connected to an $H^{\prime}$ edge. Again, if this edge connects more than distance 2 to the right, or goes off the path, we have a spanner-end. If instead this second $H^{\prime}$ edge connects distance 2 away, observe that we now have a diamond configuration on the right hand side of $e$. This is illustrated in Fig. 13.

Notice that the $M$ edge to the right of this diamond cannot be in $H^{\prime}$, and that any $H^{\prime}$ or $H^{\prime}$-$M$-$H^{\prime}$ path crossing it would have to cross $e$ as well. Thus, we may repeat our argument for this new $M\backslash H^{\prime}$ edge. Since $G$ is finite, we must eventually choose a spanner end on the right side. We extend this argument to the left side of $e$ by noting that any $H^{\prime}$ edge going off of $P$ on the left cannot be incident to any $H^{\prime}$-$M$ path off of $P$ on the right of $e$ by assumption. ∎

Assume the same conditions and fix $P$ as in Lemma 4.11. Note that such an $M-H$ alternating chain must exist, or else $\mu(G)=\nu(G)$. Then $P$ contains some $M\backslash H^{\prime}$ edge by (v) of Lemma 4.9. Consider the leftmost of these edges $e_{0}$. The left vertex $v_{0}$ of $e_{0}$ must be incident to some $H^{\prime}$ edge. If this edge does not connect $v_{0}$ to some vertex on the right of $v_{0}$ and is not part of an $H^{\prime}$-$M$-$H^{\prime}$ path connecting to the right of $v_{0}$, then Lemma 4.11 implies the existence of a spanner or diamond spanner. Otherwise, we may assume it is an $H^{\prime}$ edge connecting back to $P$, since we will derive contradictions by the illegal even cycles described in (vi) of Lemma 4.9. This $H^{\prime}$ edge connects to some vertex to the right of $v_{0}$, observe that if this $H^{\prime}$ connects directly to the left of some $M$ edge that we have created an even cycle forbidden by Lemma 4.9. This cycle is pictured in Fig. 14.

This $H^{\prime}$ edge must then connect to the left of some $M$ edge $e_{1}$ by a vertex $v_{1}$. Note $e_{1}$ cannot be in $H^{\prime}$. If none of the vertices between $v_{0}$ and $v_{1}$ are linked by an $H^{\prime}$ or $H^{\prime}$-$M$-$H^{\prime}$ path to some vertex on the right of $v_{1}$, then Lemma 4.11 again gives us a spanner or diamond spanner. The barrier is drawn in Fig. 15.

Suppose instead that one of these vertices is linked to the right of $v_{1}$. Choose the vertex between $v_{0}$ and $v_{1}$ that is connected by such a path that travels the furthest to the right. Call this vertex $v^{\prime}_{2}$ and the vertex it is linked to $v_{2}$. If $v^{\prime}_{2}$ is on the left of an $M$ edge and $v_{2}$ on the right of an $M$ edge, then the two paths between $v_{2}$ and $v_{2}^{\prime}$ form another prohibited even cycle. If $v^{\prime}_{2}$ is on the right of an $M$ edge and $v_{2}$ on the right of an $M$ edge, then the cycle connecting $v^{\prime}_{2}$ to $v_{2}$ to $v_{1}$ to $v_{0}$ is also prohibited. This forbidden cycle is shown in Fig. 16.

Thus, $v_{2}$ must also be on the left of some $M\backslash H^{\prime}$ edge $e_{2}$. By a similar argument to the case for $v_{1}$, if no vertex between $v_{0}$ and $v_{2}$ is linked to a vertex of $P$ on the right of $v_{2}$ by an $H^{\prime}$ or $M$-$H^{\prime}$-$M$ path, then Lemma 4.11 applies. Thus, some vertex between $v_{0}$ and $v_{2}$ must be linked to the right of $v_{2}$. In fact, by choice of $v_{2}$ being furthest away of all linked vertices from those between $v_{0}$ and $v_{1}$, we may restrict out attention to the vertices between $v_{1}$ and $v_{2}$. Among these, again choose the vertex $v_{3}^{\prime}$ that is linked the furthest to the right to some vertex $v_{3}$, as shown in Fig. 17.

Again, if $v_{3}^{\prime}$ is to the left of an $M$ edge and $v_{3}$ to the right, then these two paths between these two vertices form a forbidden even cycle. If instead $v_{3}^{\prime}$ is on the right of an $M$ edge and $v_{3}$ on the right, then these two vertices are part of another forbidden even cycle, regardless of whether $v_{2}^{\prime}$ is on the left or right of an $M$ edge. Thus, $v_{3}$ is on the left of an $M$ edge $e_{3}$. We may continue arguing in this manner, but observe that there are only finitely many $M\backslash H^{\prime}$ edges in $P$, so eventually, we will not be able to cross some $M\backslash H^{\prime}$ edge $e_{n}$ without creating a prohibited cycle. No vertex to the right of $e_{n}$ can be linked to a vertex to the left since our $H^{\prime}$ and $H^{\prime}$-$M$-$H^{\prime}$ paths were chosen to reach the furthest. Then $e_{n}$ witnesses a spanner or diamond spanner by Lemma 4.11. ∎