The concept of k-extendability is a fundamental notion in matching theory and is closely related to factor-criticality. In a seminal work, Zhang et al. established sharp conditions under which these two concepts are equivalent. In this paper, we study the equivalence between extendability and factor-criticality from the perspective of Sachs subgraphs and discuss conditions under which these notions are equivalent.
A spanning subgraph of a graph \(G\) is called a Sachs subgraph if each of its components is a regular graph of degree one or two. Such subgraphs arise naturally in the study of determinants and permanents of adjacency matrices [8, 14]. They are also known as \(\{1,2\}\)-factors and are closely related to perfect \(2\)-matchings. Note that every perfect matching is a Sachs subgraph, since all its components are copies of \(K_2\). Graphs admitting a Sachs subgraph can be characterized as follows.
Theorem 1.1([16]).A graph \(G\) has a Sachs subgraph if and only if \[i(G-S)\le |S|,\] for all \(S\subset V(G)\).
Theorem 1.1 was originally proved by Tutte in [16]; later, a short proof was given in [1].
A graph of order \(n\) is said to be \(k\)–factor-critical \((0\le k<n)\) if the removal of any \(k\) vertices results in a graph with a perfect matching. These graphs were introduced independently by Favaron [6] and Yu [13]. A graph \(G\) is \(k\)-Sachs critical if the removal of any \(k\) vertices results in a graph with a Sachs subgraph \((0\le k<n)\), this concept was introduced in [9].
A graph \(G\) is said to be \(k\)–extendable, for \(0 \le k \le \frac{|{G}|-2}{2}\), if \(G\) is connected, contains a matching of size \(k\), and every matching of size \(k\) in \(G\) is contained in a perfect matching of \(G\).
Motivated by this notion, we introduce the following analogue in the context of Sachs subgraphs. A graph \(G\) is said to be \(k\)-Sachs extendable, for \(2 \le k \le n\), if \[\exists S\subset V(G), |S|=k,G[S]\text{ has a Sachs subgraph,}\] and, for every \(S\subseteq V(G)\) with \(|S|=k\), \[\left(G[S]\text{ has a Sachs subgraph}\right)\Rightarrow\left(G-S\text{ has a Sachs subgraph}\right).\]
In factor theory, and particularly in matching theory, the notion of extendability always starts from the existence of a smaller factor and then requires that every such object can be extended to a spanning one. In the classical setting, this smaller object is a matching of size \(k\). In the Sachs setting, the natural analogue is therefore a set \(S\subseteq V(G)\), \(|S|=k\), such that \(G[S]\) has a Sachs subgraph. Thus, the condition \[\exists S\subseteq V(G),\ |S|=k,\ \text{such that }G[S]\text{ has a Sachs subgraph},\] plays exactly the same role as the requirement that \(G\) contains a matching of size \(k\), while the condition that \(G-S\) has a Sachs subgraph for every such set \(S\) is precisely the corresponding extension property. In this sense, our definition of \(k\)-Sachs extendability is the most natural analogue of classical \(k\)-extendability.
In [17], the equivalence between extendability and factor-criticality is investigated. In particular, the following results are established.
Theorem 1.2([17]).If \(k\ge\frac{|G+2|}{4}\), then a non-bipartite graph \(G\) is \(k\)-extendable if and only if it is \(2k\)-factor-critical.
It is also shown in [17] that the bound is best possible.
In this paper, we study the equivalence between extendability and factor-criticality from the perspective of Sachs subgraphs. More precisely, we aim to establish conditions guaranteeing the equivalence between \(k\)-Sachs critical graphs and \(k\)-Sachs extendable graphs.
The paper is organized as follows. In Section 1 we present the general context and introduce the basic concepts. In Section 2 we fix the notation. In Section 3, Section 4 and Section 5 we prove the main results, and in Section 6 we state some open problems.
All graphs considered in this paper are finite, undirected, and simple. For any undefined terminology or notation, we refer the reader to Lovász and Plummer [12] or Diestel [4].
Let \(G = (V, E)\) be a simple graph, where \(V = V(G)\) is the finite set of vertices and \(E = E(G)\) is the set of edges, with \(E \subseteq \{\{u, v\} : u, v \in V, u \neq v\}\). We denote the edge \(e=\{u, v\}\) as \(uv\). A subgraph of \(G\) is a graph \(H\) such that \(V(H) \subseteq V(G)\) and \(E(H) \subseteq E(G)\). A subgraph \(H\) of \(G\) is called a spanning subgraph if \(V(H) = V(G)\).
Let \(e \in E(G)\) and \(v \in V(G)\). We define \(G – e := (V, E \setminus \{e\})\) and \(G – v := (V \setminus \{v\}, \{uw \in E : u,w \neq v\})\). If \(X \subseteq V(G)\), the induced subgraph of \(G\) by \(X\) is the subgraph \(G[X]=(X,F)\), where \(F:=\{uv \!\in\! E(G) : u, v \!\in \! X\}\).
The number of vertices in a graph \(G\) is called the order of the graph and denoted by \(\left|G\right|\). A cycle in \(G\) is called odd (resp. even) if it has an odd (resp. even) number of edges. For two graphs \(G\) and \(H\), we denote by \(G\vee H\) the join of \(G\) and \(H\), that is, the graph obtained from the disjoint union of \(G\) and \(H\) by adding all possible edges between \(V(G)\) and \(V(H)\).
For a vertex \(v\in V(G)\), the neighborhood of \(v\) is \[N_G(v)=\{u\in V(G): uv\in E(G)\}.\]
When no confusion arises, we write \(N(v)\) instead of \(N_G(v)\). For a set \(S\subseteq V(G)\), the neighborhood of \(S\) is \[N_G(S)=\bigcup_{v\in S} N_G(v).\]
The degree of a vertex \(v\in V(G)\) is \(\deg_G(v)=|N_G(v)|.\) The minimum degree of \(G\) is \(\delta(G)=\min\{\deg_G(v): v\in V(G)\}.\) A graph \(G\) is called \(r\)-regular if \(\deg_G(v)=r\) for every \(v\in V(G)\). A vertex \(v\in V(G)\) is called an isolated vertex if \(\deg_G(v)=0.\) The number of isolated vertices of a graph \(G\) is denoted by \(i(G)\). We denote by \(\text{odd}(G)\) the number of odd components of \(G\). A graph \(G\) is called \(r\)-connected if \(|G|>r\) and \(G-S\) is connected for every subset \(S\subset V(G)\) with \(|S|<r\). The connectivity of \(G\), denoted by \(\kappa(G)\), is the largest integer \(r\) such that \(G\) is \(r\)-connected.
A matching \(M\) in a graph \(G\) is a set of pairwise non-adjacent edges. The matching number of \(G\), denoted by \(\mu(G)\), is the maximum cardinality of any matching in \(G\). Matchings induce an involution on the vertex set of the graph: \(M:V(G)\rightarrow V(G)\), where \(M(v)=u\) if \(uv \in M\), and \(M(v)=v\) otherwise. If \(S, U \subseteq V(G)\) with \(S \cap U = \emptyset\), we say that \(M\) is a matching from \(S\) to \(U\) if \(M(S) \subseteq U\). A matching \(M\) is perfect if \(M(v)\neq v\) for every vertex of the graph.
A vertex set \(S \subseteq V\) is independent if, for every pair of vertices \(u, v \in S\), we have \(uv \notin E\). The number of vertices in a maximum independent set is denoted by \(\alpha(G)\). A bipartite graph is a graph whose vertex set can be partitioned into two disjoint independent sets. A graph \(G\) is hamiltonian if it contains a cycle that passes through all vertices of \(G\) exactly once.
A graph is said to be of even (resp. odd) order if it has an even (resp. odd) number of vertices.
In [15], Tutte proved his well-known theorem characterizing graphs with a perfect matching:
Theorem 3.1([15]).A graph \(G\) has a perfect matching if and only if \[\text{odd}(G-S)\le |S|,\] for all \(S\subset V(G)\).
In [6], the Tutte condition was modified to characterize \(k\)-factor-critical graphs.
Theorem 3.2([6]). A graph \(G\) is a \(k\)-factor-critical graph if and only if \[\text{odd}(G-S)\le |S|-k,\] for all \(S\subset V(G)\) with \( |S|\ge k\).
Similar ideas allow one to refine Theorem 1.1 in order to easily obtain the following characterization of \(k\)-Sachs critical graphs.
Theorem 3.3([9]).A graph \(G\) is \(k\)-Sachs critical if and only if \[i(G-S)\le |S|-k,\] for all \(S\subset V(G)\) such that \(|S|\ge k\).
In 1952, Dirac presented the following famous sufficient condition for a graph to be Hamiltonian.
Theorem 3.4([5]).Every graph \(G\) of order \(n\ge3\) with \(\delta(G)\ge\frac{n}{2}\) is Hamiltonian.
Theorem 3.5. Let \(G\) be an \((n-k)\)-Sachs critical graph of order \(n\). Then \(G\) is \(k\)-Sachs extendable if and only if it is a \(k\)-Sachs critical graph.
Proof. As \(G\) is \((n-k)\)-Sachs critical, there exists \(S\subset V(G)\) with \( |S|=k\) such that \(G[S]\) has a Sachs subgraph. If, in addition, \(G\) is a \(k\)-Sachs critical graph, then for every \(T\subset V(G)\) with \(|T|=k\) it holds that \(G-T\) has a Sachs subgraph, in particular \(G\) is a \(k\)-Sachs extendable graph.
Let \(S \subset V(G)\) be a set with \(|S| = k\). Since \(|{G-S}| = n-k\), we have that \(G – V(G-S) = G[S]\) contains a Sachs subgraph, because \(G\) is \((n-k)\)-Sachs critical. Moreover, since \(G\) is \(k\)-Sachs extendable, it follows that \(G-S\) has a Sachs subgraph. Therefore, \(G\) is a \(k\)-Sachs critical graph. ◻
An immediate consequence of Theorem 3.4 is the following fact.
Corollary 3.6. Let \(G\) be a graph such that \(\delta(G) \ge \frac{n}{2}\). Then \(G\) contains a Sachs subgraph.
We now derive sufficient minimum degree conditions ensuring Sachs criticality.
Lemma 3.7. If \(G\) is a graph of order \(n\) such that \(\delta(G) \ge \frac{n+k}{2}\), then \(G\) is \(k\)-Sachs critical.
Proof. Let \(S \subset V(G)\) with \(|S| = k\). Then \[\delta(G-S) \ge \delta(G) – k \ge \frac{n+k}{2} – k = \frac{n-k}{2}.\]
Since \(|{G-S}| = n-k\), it follows from Corollary 3.6 that \(G-S\) contains a Sachs subgraph. Hence, \(G\) is a \(k\)-Sachs critical graph. ◻
Corollary 3.8. If \(G\) is a graph of order \(n\) such that \(\delta(G) \ge \frac{2n-k}{2}\), then \(G\) is \((n-k)\)-Sachs critical.
Therefore, from Corollary 3.8 and Theorem 3.5, we obtain the following bound on \(\delta(G)\) that guarantees the equivalence between extendability and criticality.
Theorem 3.9. Let \(G\) be a graph of order \(n\) with \(\delta(G) \ge \left\lceil \frac{2n-k}{2}\right\rceil\). Then \(G\) is \(k\)-Sachs extendable if and only if it is a \(k\)-Sachs critical graph.
The bound \(\left\lceil \frac{2n-k}{2}\right\rceil\) in Theorem 3.9 is sharp in the following sense.
Theorem 3.10(Sharpness of the minimum degree bound).For every integer \(k\ge 2\), there exists a graph \(G\) of order \(n\) such that \[\delta(G)=\left\lceil \frac{2n-k}{2}\right\rceil -1,\] \(G\) is \(k\)-Sachs extendable, but \(G\) is not a \(k\)-Sachs critical graph.
Proof. We distinguish two cases according to the parity of \(k\).
Case 1. \(k\ge 3\) is odd.
Let \(k\ge 3\) be odd and set \(n=k+2\). Define \[t=\frac{n-1}{2}=\frac{k+3}{2}.\] Let \(G=K_{t,t}\vee K_{1}\) be the graph obtained from the complete bipartite graph \(K_{t,t}\) by adding a new vertex \(x\) adjacent to all vertices of \(K_{t,t}\). Let \((A,B)\) be the bipartition of \(K_{t,t}\). Clearly, \[|V(G)|=2t+1=n.\]
For every vertex \(v\in A\cup B\) we have \(\deg(v)=t+1\), while \(\deg(x)=2t\). Hence, \[\delta(G)=t+1.\]
Since \(n\) is odd, we compute \[\left\lceil \frac{2n-k}{2}\right\rceil -1 =\left\lceil \frac{n+2}{2}\right\rceil -1 =\frac{n+3}{2}-1 =\frac{n+1}{2} =t+1 =\delta(G).\]
We next show that \(G\) is not \(k\)-Sachs critical. Indeed, if \(u,v\in A\) are two distinct vertices, then \(uv\notin E(G)\). Let \[S=V(G)\setminus\{u,v\}.\]
Then \(|S|=n-2=k\), and the graph \(G-S\) has no Sachs subgraph. Therefore, \(G\) is not \(k\)-Sachs critical.
We now prove that \(G\) is \(k\)-Sachs extendable. Let \(T\subseteq V(G)\) with \(|T|=k\) such that the induced subgraph \(G[T]\) contains a Sachs subgraph. Suppose, for a contradiction, that \(G-T\) has no Sachs subgraph. Since \(|V(G-T)|=2\), both vertices of \(G-T\) belong to \(A\cup B\); without loss of generality, assume that \(V(G-T)\subseteq A\).
Define \[X=(A\setminus V(G-T))\cup\{x\}.\]
Then \[|X|=|A|-2+1=|A|-1,\] and \[i(G[T]-X)=|B|>|A|-1=|X|.\]
Applying Theorem 1.1 to the induced subgraph \(G[T]\), we obtain a contradiction, since \(i(G[T]-X)>|X|\). Thus, the graph \(G[T]\) has no Sachs subgraph, contrary to the choice of \(T\). Hence, \(G-T\) contains a Sachs subgraph and \(G\) is \(k\)-Sachs extendable.
Case 2. \(k\ge 2\) is even.
Let \(k\ge 2\) be even and set \(n=k+2\). Define \(t=\frac{n}{2}\) and let \[G=K_{t,t}.\]
Then \(|V(G)|=n\) and \(\delta(G)=t=\frac{n}{2}\). Moreover, \[\left\lceil \frac{2n-k}{2}\right\rceil -1 =\left\lceil \frac{n+2}{2}\right\rceil -1 =\frac{n+2}{2}-1 =\frac{n}{2} =\delta(G).\]
To see that \(G\) is not \(k\)-Sachs critical, let \(u,v\in V(G)\) be two distinct vertices such that \(uv\notin E(G)\). Setting \[S=V(G)\setminus\{u,v\},\] we obtain \(|S|=n-2=k\) and the graph \(G-S\) has no Sachs subgraph. Hence, \(G\) is not \(k\)-Sachs critical.
Finally, we show that \(G\) is \(k\)-Sachs extendable. Let \(T\subseteq V(G)\) with \(|T|=k\) such that \(G[T]\) contains a Sachs subgraph, and suppose that \(G-T\) has no Sachs subgraph. Since \(|V(G-T)|=2\), both vertices of \(G-T\) lie in the same part of the bipartition \((A,B)\) of \(G\); without loss of generality, assume \(V(G-T)\subseteq A\).
Let \[X=A\setminus V(G-T).\]
Then \(|X|=|A|-2\) and \[i(G[T]-X)=|B|>|A|-2=|X|.\]
Applying Theorem 1.1 to the induced subgraph \(G[T]\), we obtain a contradiction, since \(i(G[T]-X)>|X|\). Thus, \(G[T]\) has no Sachs subgraph, contrary to the choice of \(T\). Therefore, \(G\) is \(k\)-Sachs extendable. This completes the proof. ◻
In contrast to Sachs-type criticality, the notions of \(k\)-extendability and \(k\)-factor-criticality enforce large connectivity. We recall some classical results in this direction.
Lemma 4.1([11]).If \(G\) is \(k\)-extendable, then \(\kappa (G)\ge k+1\).
Lemma 4.2([10]).If \(G\) is a \(k\)-extendable graph with \(k\ge \frac{n}{4}\), then either \(G\) is bipartite or \(\kappa (G)\ge 2k\).
Theorem 4.3([6]).If \(G\) is a \(k\)-factor-critical graph, then \(\kappa (G)\ge k\).
The \(k\)-Sachs criticality and extendability do not impose, in general, large connectivity. In particular, this notion does not force connectivity linear in \(k\), not even when \[k \ge \frac{n}{4}.\]
The next example shows that no linear connectivity bound in \(k\) can be expected in general.
Example 4.4. Let \(A \cong K_{k+2}\) and \(B \cong K_{k+2}\) be two disjoint cliques, and let \(x\) be a vertex adjacent to all vertices of \(A \cup B\). No edges are added between \(A\) and \(B\). The resulting graph \(G\) has order \(n = 2k+5\) and vertex-connectivity \(\kappa(G)=1\). In particular, we have \(k > n/4\).
Nevertheless, \(G\) is \(k\)-Sachs critical. Indeed, for every set \(S \subseteq V(G)\) with \(|S| = k\), each of the parts \(A \setminus S\) and \(B \setminus S\) has at least two vertices and, therefore, admits a Sachs subgraph. This allows one to construct a Sachs subgraph that covers all vertices of \(G – S\).
This example shows that the connectivity jump phenomena known for \(k\)-extendable graphs do not carry over to the context of Sachs-type criticality.
Despite this, \(k\)-Sachs criticality does impose a strong structural restriction on small vertex cuts. In particular, the deletion of few vertices cannot isolate small subgraphs: every resulting component must have size linear in \(k\). This fact is formalized in the following result.
Observation 4.5. If \(G\) is a \(k\)-Sachs critical graph, then \(\delta(G)\ge k+1\).
Proof. Suppose, to the contrary, that there exists a vertex \(v\in V(G)\) with \(\deg(v)\leq k\). Let \(S\subseteq V(G)\setminus\{v\}\) be a set of cardinality \(k\) containing \(N(v)\). Then \(v\) is an isolated vertex of \(G-S\), and hence \(G-S\) has no Sachs subgraph. This contradicts the fact that \(G\) is \(k\)-Sachs critical. Therefore, \(\delta(G)\geq k+1\). ◻
Theorem 4.6. Let \(G\) be a \(k\)-Sachs critical graph of order \(n\), and let \(T \subseteq V(G)\) with \(|T| = t < k\). Then every connected component \(C\) of \(G – T\) satisfies \[|C| \ge k – t + 1.\]
Moreover, the number of connected components of \(G – T\) is at most \[\frac{n – t}{k – t + 1}.\]
Proof. Suppose, to the contrary, that there exists a set \(T \subseteq V(G)\) with \(|T|=t<k\) and a connected component \(C\) of \(G-T\) such that \(|C|\le k-t\). Let \(v\in V(C)\) be an arbitrary vertex.
We construct a set \(S\subseteq V(G)\) of size \(k\) as follows: we take all vertices of \(T\), all vertices of \(C\) except \(v\), and complete with arbitrary vertices from \(V(G)\setminus (T\cup C)\) until obtaining \(|S|=k\). This is possible since \[|T|+(|C|-1)\le t+(k-t-1)=k-1.\]
In the graph \(G-S\), the vertex \(v\) becomes isolated, since all its neighbors belong to \(T\) or to \(C\setminus\{v\}\), which have been deleted. Consequently, \(G-S\) does not admit a Sachs subgraph covering all its vertices, contradicting the assumption that \(G\) is \(k\)-Sachs critical.
Therefore, every connected component \(C\) of \(G-T\) satisfies \(|C|\ge k-t+1\).
For the second assertion, let \(c\) be the number of connected components of \(G-T\). Since each of them has at least \(k-t+1\) vertices, we have \[n-t = |V(G-T)| \ge c\,(k-t+1),\] and hence \[c \le \frac{n-t}{k-t+1}.\]
This completes the proof. ◻
Theorem 4.7. Let \(G\) be a graph of order \(n\), and let \(k \ge \frac{2}{3}(n-1).\) Then \(G\) is \(k\)-Sachs critical if and only if \(G\) is \(k\)-Sachs extendable and \(\delta(G)\ge k+1.\)
Proof. Suppose that \(G\) is \(k\)-Sachs extendable and \(\delta(G)\ge k+1\). Since \(k \ge \frac{2}{3}(n-1)\), we have \[\delta(G)\ge \frac{2}{3}(n-1)+1=\frac{2n+1}{3}.\]
On the other hand, \[\frac{2n-k}{2}\le \frac{2n-\frac{2}{3}(n-1)}{2} =\frac{\frac{4n}{3}+\frac{2}{3}}{2} =\frac{2n+1}{3}\le \delta(G).\]t
Therefore, by Theorem 3.9, \(G\) is \(k\)-Sachs critical.
Conversely, suppose that \(G\) is \(k\)-Sachs critical. Then Observation 4.5 implies that \(\delta(G)\ge k+1\), and arguing as above, we obtain \[\frac{2n-k}{2}\le \delta(G).\]
Hence, by Corollary 3.8, \(G\) is an \((n-k)\)-Sachs critical graph. Therefore, there exists a set \(S\subseteq V(G)\) with \(|S|=n-k\) such that \(G-S\) contains a Sachs subgraph. Since \(|G-S|=k\), this proves the existential part of the definition of \(k\)-Sachs extendability.
Now let \(T\subseteq V(G)\) with \(|T|=k\) be such that \(G[T]\) has a Sachs subgraph. Since \(G\) is \(k\)-Sachs critical, it follows that \(G-T\) has a Sachs subgraph. Thus, the universal implication in the definition also holds, and therefore \(G\) is \(k\)-Sachs extendable. ◻
In this section we restrict our attention to OCP graphs, where Sachs subgraphs interact particularly well with perfect matchings.
A graph is said to have the odd cycle property if whenever two odd cycles are disjoint, they are connected by an edge; in this case, we say that the graph is OCP. The OCP graphs are known to form a family that extends Hall’s theorem [2] and are important in factor theory [3, 7].
Lemma 5.1. An OCP graph of even order with a Sachs subgraph has a perfect matching.
Proof. Let \(G\) be an OCP graph of even order with a Sachs subgraph \(H\). Let \(C_{1},\dots,C_{k}\) be the odd cycles of \(H\). Since \(|G|\) is even, it follows that \(k\) is even. If \(k=0\), then every component of \(H\) is even, and hence \(H\) has a perfect matching. So assume \(k\geq 2\). Write \(t=\frac{k}{2}\).
Let \(X\) be the set of vertices of \(H\) that lie in an even component of \(H\), and let \(M\) be a perfect matching of \(H[X]\). For each \(i=1,\dots,t\), since \(G\) is OCP, there exists an edge \(e_i=u_iv_i\in E(G)\) joining \(C_i\) and \(C_{t+i}\), with \(u_i\in V(C_i)\) and \(v_i\in V(C_{t+i})\). Since \(C_i-u_i\) and \(C_{t+i}-v_i\) are even paths, they admit perfect matchings \(M_i\) and \(N_i\), respectively.
Then \[M\cup\bigcup_{i=1}^{t}\left(M_i\cup N_i\cup\{e_i\}\right),\] is a perfect matching of \(G\). ◻
Theorem 5.2. Let \(G\) be an OCP graph of order \(n\) such that \(n-k\) is even. Then \(G\) is a \(k\)-Sachs critical graph if and only if \(G\) is a \(k\)-factor-critical graph.
Proof. \((\Rightarrow)\) Let \(S\subseteq V(G)\) with \(|S|=k\). Since \(G\) is \(k\)-Sachs critical, the graph \(G-S\) admits a Sachs subgraph. Moreover, \(|V(G-S)|=n-k\) is even and \(G-S\) is an OCP graph; hence, by Lemma 5.1, it follows that \(G-S\) has a perfect matching. Therefore, \(G\) is \(k\)-factor-critical.
\((\Leftarrow)\) If \(G\) is \(k\)-factor-critical, then for every set \(S\subseteq V(G)\) with \(|S|=k\) the graph \(G-S\) has a perfect matching, which is in particular a Sachs subgraph. Hence, \(G\) is \(k\)-Sachs critical. ◻
Theorem 5.3. Let \(G\) be a connected OCP graph of even order. Then \(G\) is a \(2k\)-Sachs extendable graph if and only if \(G\) is a \(k\)-extendable graph.
Proof. \((\Rightarrow)\) Suppose that \(G\) is connected and \(2k\)-Sachs extendable. We first note that \(G\) contains a matching of size \(k\). Indeed, by \(2k\)-Sachs extendability there exists a set \(S\subseteq V(G)\) with \(|S|=2k\) such that \(G[S]\) contains a Sachs subgraph; since \(G[S]\) is an OCP graph and of even order, by Lemma 5.1 the graph \(G[S]\) has a perfect matching, and in particular \(G\) contains a matching of size \(k\).
Let \(M\) be a matching of size \(k\) in \(G\) and let \(S:=V(M)\), so that \(|S|=2k\) and \(G[S]\) contains a Sachs subgraph (namely, \(M\)). By \(2k\)-Sachs extendability, the graph \(G-S\) contains a Sachs subgraph. Since \(G\) is OCP and of even order, the graph \(G-S\) is also OCP and of even order; by Lemma 5.1, \(G-S\) has a perfect matching \(M'\). Then \(M\cup M'\) is a perfect matching of \(G\) containing \(M\). Hence every matching of size \(k\) in \(G\) extends to a perfect matching of \(G\). Since \(G\) is connected, it follows that \(G\) is \(k\)-extendable.
\((\Leftarrow)\) Suppose that \(G\) is \(k\)-extendable. First, there exists a matching \(M\) of size \(k\); taking \(S:=V(M)\) we obtain \(|S|=2k\) and \(G[S]\) contains a Sachs subgraph, so the existential condition of \(2k\)-Sachs extendability is satisfied.
Now let \(S\subseteq V(G)\) with \(|S|=2k\) such that \(G[S]\) contains a Sachs subgraph. Since \(G[S]\) is OCP and of even order, by Lemma 5.1 the graph \(G[S]\) has a perfect matching \(F_S\). In particular, \(F_S\) is a matching of size \(k\) in \(G\), and by \(k\)-extendability it extends to a perfect matching \(F\) of \(G\). Then \(F\setminus F_S\) is a perfect matching of \(G-S\), and therefore \(G-S\) contains a Sachs subgraph. We conclude that \(G\) is \(2k\)-Sachs extendable. ◻
Therefore, from Theorem 1.2, the following result is obtained.
Theorem 5.4. Let \(G\) be a connected non-bipartite OCP graph of even order \(n\). If \(k\geq \frac{n+2}{4}\), then \(G\) is \(2k\)-Sachs extendable if and only if it is \(2k\)-Sachs critical.
Proof. By Theorem 5.3, \(G\) is \(2k\)-Sachs extendable if and only if it is \(k\)-extendable. Since \(G\) is non-bipartite and \(k\geq \frac{n+2}{4}\), Theorem 1.2 implies that \(G\) is \(k\)-extendable if and only if it is \(2k\)-factor-critical. Finally, since \(n-2k\) is even, Theorem 5.2 yields that \(G\) is \(2k\)-factor-critical if and only if it is \(2k\)-Sachs critical. Therefore, \(G\) is \(2k\)-Sachs extendable if and only if it is \(2k\)-Sachs critical. ◻
We close the paper with the following natural problem concerning the extremal graphs for Theorem 3.9.
Problem 6.1. Classify the extremal graphs showing the sharpness of Theorem 3.9. More precisely, describe the graphs \(G\) satisfying \[\delta(G)=\left\lceil \frac{2n-k}{2}\right\rceil-1,\] that are \(k\)-Sachs extendable but not \(k\)-Sachs critical.
We thank the referee for the careful reading and helpful suggestions.
Data sharing not applicable to this article as no datasets were generated or analyzed during the current study.
The authors declare that they have no conflict of interest.