Several graph decompositions that factorize the determinant of the adjacency matrix isolate a Kőnig–Egerváry part, such as the SD–KE decomposition and the critical independence decomposition of Larson. This suggests that the study of graph unimodularity can be approached, to a large extent, through the structure of Kőnig–Egerváry graphs. In this paper, we advance this point of view by introducing a new determinant factorization within the class of Kőnig–Egerváry graphs. More precisely, given a Kőnig–Egerváry graph \(G\), we consider the partition of \(V(G)\) into its perfect-flower part \(PF(G)\) and its perfect-flower-free part \(PFF(G)\), and prove that \[\det(G)=\det(G[PF(G)])\det(G[PFF(G)]).\] We also obtain the analogous factorization for the permanent. This decomposition provides a new tool for the study of unimodularity, reducing the problem to two induced subgraphs of very different nature: the graph \(G[PF(G)]\), whose structure is closely related to Sterboul–Deming configurations with perfect matchings, and the graph \(G[PFF(G)]\), which is governed by the theory of critical independent sets. In this way, the paper provides a new structural framework for the study of unimodular graphs through Kőnig–Egerváry theory.
Let \(\alpha(G)\) denote the cardinality of a maximum independent set, and let \(\mu(G)\) denote the size of a maximum matching in \(G=(V,E)\). It is known that \(\alpha(G)+\mu(G)\) may equal the order of \(G\); in this case, \(G\) is called a Kőnig–Egerváry graph [3, 7, 28]. Kőnig–Egerváry graphs have been extensively studied [2, 9, 17, 18, 10]. It is also known that every bipartite graph is a Kőnig–Egerváry graph [6]. These graphs were independently introduced by Deming [3], Sterboul [28], and Gavril [7].
In this paper, the term subgraph is understood as a subgraph defined by a graph together with a given matching in that graph. In [5], Edmonds introduced the following concepts relative to a matching \(M\) of a graph \(G\) and its subgraphs. An \(M\)-blossom of \(G\) is an odd cycle of length \(2k+1\) with \(k\) edges in \(M\). The vertex not saturated by \(M\) in the cycle is called the base of the blossom. An \(M\)-stem is an \(M\)-alternating path of even length, possibly zero, connecting the base of the blossom with a vertex not saturated by \(M\) in \(G\). The base is the only common vertex between the blossom and the stem. An \(M\)-flower is a blossom joined with a stem. The vertex not saturated by \(M\) in the stem is called the root of the flower.
In [28], Sterboul introduced the concept of a posy for the first time. An \(M\)-posy consists of two, not necessarily disjoint, \(M\)-blossoms joined by an \(M\)-alternating path that starts and ends with edges in \(M\). The endpoints of the path are the bases of the two blossoms. There are no internal vertices of the path in the blossoms.
Sterboul [28] was the first to characterize Kőnig–Egerváry graphs by forbidden configurations relative to a maximum matching. Subsequently, Korach, Nguyen, and Peis [15] reformulated this characterization in terms of simpler configurations, unifying the structures of flowers and posies. Later, Bonomo et al. [1] obtained a purely structural characterization based on forbidden subgraphs. More recently, in [11, 13, 14], results were obtained that simplify working with flower and posy structures.
Theorem 1.1 ([28]).For a graph \(G\), the following properties are equivalent:
\(G\) is a non-Kőnig–Egerváry graph.
For every maximum matching \(M\), there exists an \(M\)-flower or an \(M\)-posy in \(G\).
For some maximum matching \(M\), there exists an \(M\)-flower or an \(M\)-posy in \(G\).
The set of vertices of \(G\) lying in a flower or posy, for any maximum matching, is denoted by \(SD(G)\), and we write \[KE(G)=V(G)-SD(G).\] The sets \(SD(G)\) and \(KE(G)\) constitute the SD–KE decomposition of the graph. A graph \(G\) is called a Sterboul–Deming graph if \(KE(G)=\emptyset\). Essentially, such a graph may be regarded as the structural counterpart of a Kőnig–Egerváry graph. Characterizations of Sterboul–Deming graphs can be found in [23].
The SD–KE decomposition admits a factorization for the determinant of the adjacency matrix of a graph [14, 22], namely \[\det(G)=\det(G[KE(G)])\det(G[SD(G)]).\]
We say that a graph is unimodular if the determinant of its adjacency matrix is \(\pm 1\). The preceding factorization naturally reduces the problem of studying the unimodularity of graphs to the study of the unimodularity of Kőnig–Egerváry graphs or Sterboul–Deming graphs. Unimodular Sterboul–Deming graphs have been studied in [12, 20]. Another graph decomposition that factorizes the determinant is the critical independence decomposition of Larson [16], which partitions a graph into a Kőnig–Egerváry graph and a \(2\)-bicritical graph [26].
In this work, we advance the study of the unimodularity of Kőnig–Egerváry graphs through decompositions.
Given a matching \(M\) of \(G\), an \(M\)–perfect flower is a pair \((C,P)\) with the following properties. The subgraph \(C\) is an odd cycle of length \(2k+1\) containing exactly \(k\) edges of \(M\). The path \(P\) is a non-trivial \(M\)-alternating path, say \[P=p_1,p_2,\ldots,p_t,\] whose first and last edges belong to \(M\). Moreover, \[V(C)\cap V(P)=\{p_1\}.\]
Thus, paths of length one are allowed in the definition of an \(M\)-perfect flower; in that case, the unique edge of the path is both the first and the last edge, and hence it must belong to \(M\). Paths of length zero are not allowed in this definition.
We define the perfect-flower part of \(G\) as the set of vertices of \(G\) that belong to some \(M\)-perfect flower, for some matching \(M\), and we denote it by \(PF(G)\). That is, \[PF(G):=\left\{v\in V(G):v\text{ belongs to an }M\text{-perfect flower for some maximum matching }M\right\}.\] We define the perfect-flower-free part of \(G\) as \[PFF(G):=V(G)-PF(G).\] This decomposition was first defined in [21] in order to study the structure of critical independent sets in Kőnig–Egerváry graphs.
In this work, we prove that, for every Kőnig–Egerváry graph \(G\), the perfect-flower decomposition of the vertex set is compatible with both the determinant and the permanent of the adjacency matrix. More precisely, if \[V(G)=PF(G)\cup PFF(G),\] then \[\det(G) = \det(G[PF(G)])\det(G[PFF(G)]),\] and \[\operatorname{perm}(G) = \operatorname{perm}(G[PF(G)]) \operatorname{perm}(G[PFF(G)]).\]
The determinant factorization is the one relevant to unimodularity. Indeed, within the class of Kőnig–Egerváry graphs, it reduces the problem of studying whether \(\det(G)=\pm1\) to the corresponding induced subgraphs \(G[PF(G)]\) and \(G[PFF(G)]\). In particular, this reduction separates two induced subgraphs with different structural features: the structure of \(G[PF(G)]\) is closely related to that of Sterboul–Deming graphs with a perfect matching [12], whereas the structure of \(G[PFF(G)]\) can be controlled through the theory of critical independent sets [21].
The permanent factorization has a complementary enumerative meaning. By the Sachs expansion recalled in Theorem 3.1, \(\operatorname{perm}(G)\) is the positive weighted sum of the Sachs subgraphs of \(G\), where a Sachs subgraph with \(m\) cycle components contributes \(2^m\). Hence, the permanent identity says that this weighted enumeration splits independently over the two parts \(PF(G)\) and \(PFF(G)\). In this sense, the permanent factorization is not merely an algebraic analogue of the determinant factorization; it records the decomposition of the Sachs structure itself.
Consequently, the present theorem should be interpreted as an internal reduction for the class of Kőnig–Egerváry graphs. For arbitrary graphs, its use should be understood in combination with previous decompositions that isolate a Kőnig–Egerváry part, such as the SD–KE decomposition discussed above or Larson’s critical independence decomposition [16]. Thus, the broader application to general graphs is indirect: the factorization proved here applies to the Kőnig–Egerváry part produced by such decompositions.
The paper is organized as follows. Section 2 contains the terminology and auxiliary results used throughout the paper. Section 3 contains the main results. Section 4 is devoted to open problems.
All graphs considered in this paper are finite, undirected, and simple. For undefined terminology or notation, we refer the reader to Lovász and Plummer [25] or Diestel [4].
Let \(G=(V,E)\) be a simple graph, where \(V=V(G)\) is the finite vertex set and \(E=E(G)\) is the edge set, with \[E\subseteq \{\{u,v\}:u,v\in V,\ u\neq v\}.\] We denote the edge \(e=\{u,v\}\) by \(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 spanning if \(V(H)=V(G)\). For two vertex sets \(X,Y\subseteq V(G)\), we denote by \(E(X,Y)\) the set of edges \(uv\in E(G)\) such that \(u\in X\) and \(v\in Y\).
Let \(e\in E(G)\) and \(v\in V(G)\). We define \[G-e:=(V,E-\{e\})\] and \[G-v:=(V-\{v\},\{uw\in E:u,w\neq v\}).\] If \(X\subseteq V(G)\), the induced subgraph of \(G\) on \(X\) is the subgraph \[G[X]=(X,F),\] where \[F:=\{uv\in E(G):u,v\in X\}.\] The union of two graphs \(G\) and \(H\) is the graph \(G\cup H\) with \[V(G\cup H)=V(G)\cup V(H) \quad\text{and}\quad E(G\cup H)=E(G)\cup E(H).\] If \(M\) is a set of edges of \(G\), we denote by \(G[M]\) the subgraph of \(G\) spanned by the edges of \(M\), that is, \[V(G[M])=\{v\in V(G): \text{$v$ is an endpoint of some edge in } M\}\] and \[E(G[M])=M.\]
The number of vertices in a graph \(G\) is called the order of the graph and is denoted by \(\left|G\right|\). A cycle in \(G\) is called odd, respectively even, if it has an odd, respectively even, number of edges.
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 a 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)\). It is well known that the symmetric difference of two matchings has a very simple structure.
Lemma 2.1. Let \(M_{1}\) and \(M_{2}\) be two maximum matchings of a graph \(G\), and let \[H=(V(M_{1}\triangle M_{2}),\,M_{1}\triangle M_{2}).\] Then every connected component of \(H\) is one of the following:
1. an even cycle whose edges alternate between \(M_{1}\) and \(M_{2}\);
2. a path of even length whose edges alternate between \(M_{1}\) and \(M_{2}\); in this case, one end-vertex is saturated by \(M_{1}\) and unsaturated by \(M_{2}\), while the other is saturated by \(M_{2}\) and unsaturated by \(M_{1}\).
In this section, we establish the main results of the paper. Before starting, we introduce the necessary tools and notation.
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, 27]. 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\). The set of all Sachs subgraphs of \(G\) is denoted by \(Sachs(G)\).
Let \(prk(G)\) be the maximum order of a subgraph \(H\) of \(G\) such that \(Sachs(H)\neq\emptyset\). We define \[Sachs^{prk}(G):=\bigcup_{H}Sachs(H),\] where the union is taken over all subgraphs of \(G\) of order \(prk(G)\). Note that when \(Sachs(G)\neq\emptyset\), we have \[Sachs^{prk}(G)=Sachs(G).\]
The following theorem shows that there is a natural relationship between the Sachs subgraphs of a graph and the computation of its determinant or permanent.
Theorem 3.1([8, 19])Let \(G\) be a graph. Then \[\begin{eqnarray*} \det(G) & = & \sum\limits_{H\in Sachs(G)}(-1)^{k(H)}2^{m(H)},\\ perm(G) & = & \sum\limits_{H\in Sachs(G)}2^{m(H)}, \end{eqnarray*}\] where \(k(H)\) is the number of even components of \(H\), and \(m(H)\) is the number of cycles of \(H\).
Denote by \(\det(G)\) the determinant \(\det(A(G))\), and define \(\det(G[\emptyset])=1\).
For the reader’s convenience, we include a short proof of Lemma 3.2 for completeness.
Lemma 3.2([24]).Let \(G\) be a Kőnig–Egerváry graph and \(H\in Sachs^{prk}(G)\). Then \(H\) has no odd cycles.
Proof. Let \(I\) be a maximum independent set of \(G\), and set \(X:=V(G)-I\). Since \(G\) is a Kőnig–Egerváry graph, we have \[|X|=|G|-\alpha(G)=\mu(G).\] Moreover, \(X\) is a vertex cover of \(G\), and therefore \(X\cap V(H)\) is a vertex cover of \(H\).
Since every maximum matching of \(G\) is a Sachs subgraph of order \(2\mu(G)\), it follows that \[prk(G)\geq 2\mu(G).\] As \(H\in Sachs^{prk}(G)\), we have \(|H|=prk(G)\), and hence \[|H|\geq 2\mu(G).\] Assume that \(H\) has an odd cycle component. Since each component of \(H\) is either a copy of \(K_2\) or a cycle, every vertex cover of \(H\) has size at least \(|H|/2\), and in fact strictly greater than \(|H|/2\) whenever \(H\) has an odd cycle component. Therefore, \[|X\cap V(H)|>\frac{|H|}{2}.\] On the other hand, \[|X\cap V(H)|\leq |X|=\mu(G)\leq \frac{|H|}{2},\] which is a contradiction. Therefore, \(H\) has no odd cycles. ◻
Corollary 3.3. Let \(G\) be a Kőnig–Egerváry graph. Then \[prk(G)=2\mu(G).\]
In general, the decomposition \(PFF(G),PF(G)\) does not respect the Sachs structure of every Kőnig–Egerváry graph in the following sense: for the graph \(G\) in Figure 1, there exists \(H\in Sachs^{prk}(G)\) such that \[E(PFF(G),PF(G))\cap E(H)\neq\emptyset.\]
Moreover, note that \(G\) satisfies \[\mu(G)+\alpha(G)=4+5=9=|G|,\] that is, \(G\) is a Kőnig–Egerváry graph. However, for Kőnig–Egerváry graphs, the graph has a perfect matching if and only if \(Sachs(G)=Sachs^{prk}(G)\). This reduces the study of the determinant and permanent of the graph via Theorem 3.1 to the study of Kőnig–Egerváry graphs with a perfect matching. Therefore, from this point of view, we are only interested in Kőnig–Egerváry graphs with a perfect matching. We will show in Theorem 3.4 that the decomposition \(PFF(G),PF(G)\) respects the Sachs structure in any Kőnig–Egerváry graph with a perfect matching.
Theorem 3.4. Let \(G\) be a Kőnig–Egerváry graph with a perfect matching. Then, for every \(H\in Sachs G\), it holds that \[E(PFF(G),PF(G))\cap E(H)=\emptyset.\]
Proof. Assume, for contradiction, that there exists \(H\in Sachs(G)\) such that \[E(PFF(G),PF(G))\cap E(H)\neq\emptyset.\] Let \[e\in E(PFF(G),PF(G))\cap E(H).\]
Since \(H\) is a Sachs subgraph, each connected component of \(H\) is either a copy of \(K_2\) or a cycle. By Lemma 3.2, \(H\) has no odd cycles, and therefore every cycle component of \(H\) is even. Hence, each cycle component has a perfect matching, and if \(e\) lies on such a cycle, we may choose a perfect matching of that cycle containing \(e\). If \(e\) belongs to a \(K_2\)-component, then it is forced to belong to the unique perfect matching of that component. Choosing arbitrarily a perfect matching on every other component of \(H\), we obtain a perfect matching \(M_e\) of \(H\) such that \(e\in M_e\). Since every Sachs subgraph is spanning by definition, it follows that \(M_e\) is also a perfect matching of \(G\).
By the choice of \(e\), there exists \(v\in PF(G)\cap e\). Note that \(M_e(v)\in PFF(G)\) and \(e=vM_e(v)\in M_e\). On the other hand, there exists a perfect matching \(M_v\) of \(G\) such that \(v\) lies in an \(M_v\)-perfect flower \((P,C)\) of \(G\), as shown in Figure 2.
Write \[C=c_1,c_2,\ldots,c_{2r+1},c_1, \qquad P=p_1,p_2,\ldots,p_t,\] where \(p_1=c_1\). The common vertex \(p_1=c_1\) is the base of the \(M_v\)-blossom \(C\); otherwise \(p_1\) would be incident with an edge of \(M_v\) in \(C\) and also with the first edge of \(P\), which belongs to \(M_v\). We orient \(P\) from \(p_1\) to its other endpoint. Thus \[p_\ell p_{\ell+1}\in M_v \quad\Longleftrightarrow\quad \ell \text{ is odd}, \qquad 1\leq \ell<t.\]
In particular, since the first and last edges of \(P\) belong to \(M_v\), the number \(t\) is even.
We also choose the cyclic orientation of \(C\) so that \[c_\ell c_{\ell+1}\in M_v \quad\Longleftrightarrow\quad \ell \text{ is even}, \qquad 1\leq \ell\leq 2r,\] and \[c_{2r+1}c_1\notin M_v.\]
Therefore \(C\) is an \(M_v\)-blossom based at \(p_1=c_1\), and \[|E(C)\cap M_v|=r=\frac{|V(C)|-1}{2}.\]
Define \[x:=M_e(v).\]
Then note that the edges \(vM_v(v)\) and \(vx\) are distinct. Set \[S:=V(P)\cup V(C).\]
Since \((P,C)\) is an \(M_v\)-perfect flower, every vertex of \(S\) is matched by \(M_v\) to another vertex of \(S\). In particular, no edge of \(M_v\) has exactly one endpoint in \(S\). By Lemma 2.1, the connected component \(K\) of \[\bigl(V(M_v\triangle M_e),\, M_v\triangle M_e\bigr),\] containing \(v\) is an even cycle whose edges alternate between \(M_v\) and \(M_e\). Since \(x=M_e(v)\notin S\), if we traverse \(K\) starting at \(v\) along the edge \(vx\in M_e\), we eventually meet a vertex of \(S\) again, because \(K\) is a cycle and \(v\in S\). Let \(u\) be the first such vertex after \(v\), and let \[Q=q_1,\dots,q_w,\] be the corresponding subpath of \(K\), where \(q_1=v\) and \(q_w=u\). By construction, \[V(Q)\cap S=\{q_1,q_w\}=\{v,u\}.\]
Moreover, \(Q\) alternates between edges of \(M_e\) and edges of \(M_v\), and its first edge is \[q_1q_2=vx\in M_e.\]
Since the internal vertices of \(Q\) lie outside \(S\) and no edge of \(M_v\) joins \(S\) to \(V(G)\setminus S\), the last edge \(q_{w-1}q_w\) cannot belong to \(M_v\). Hence \[q_{w-1}q_w\in M_e.\]
Therefore, \[q_\ell q_{\ell+1}\in M_e \quad\Longleftrightarrow\quad \ell \text{ is odd},\] and \[q_\ell q_{\ell+1}\in M_v \quad\Longleftrightarrow\quad \ell \text{ is even}, \qquad 1\leq \ell<w.\]
In particular, \(w\) is even. Since \(q_2=x\notin V(P)\cup V(C)\) and \(q_w=u\in V(P)\cup V(C)\), we have \(w\geq 4\). Hence \(q_3\) is defined and \[q_3\notin V(P)\cup V(C).\]
We now consider the possible positions of \(v\) and \(u\) in \(V(P)\cup V(C)\). We keep the roles of \(v\) and \(u\) fixed throughout the argument: the vertex \(v\) is the endpoint of \(e\) that belongs to \(PF(G)\), whereas \(x=q_2=M_e(v)\) is the vertex that must be forced to belong to \(PF(G)\). Thus no case below is obtained by interchanging \(u\) and \(v\).
In each case, we explicitly identify an odd cycle \(D\) which is an \(M\)-blossom for the relevant perfect matching \(M\), and an \(M\)-alternating path \(R\) whose first and last edges belong to \(M\). We also check that \(V(D)\cap V(R)\) consists of exactly one vertex.
Case 1. Assume that \(v\in V(P)\), say \(v=p_{i}\) for some odd \(i\). According to the position of the vertex \(u\), we consider the following subcases.
Case 1.1. Assume that \(u\in V(P)\), say \(u=p_j\) for some even \(j\), see Figure 3. Consider the path \[R:=p_1,p_2,\ldots,p_j(=q_w),q_{w-1},q_{w-2},\ldots,q_2 .\]
The cycle \(C\) is an \(M_v\)-blossom based at \(p_1=c_1\). Let us check that \(R\) is a valid attaching path. Its first edge is \(p_1p_2\in M_v\). Since \(j\) is even, the edge \(p_{j-1}p_j\) also belongs to \(M_v\). The next edge, namely \(q_wq_{w-1}\), does not belong to \(M_v\), because \(q_{w-1}q_w\in M_e\). Along the reversed part of \(Q\), the edges alternate with respect to \(M_v\), and the last edge \(q_3q_2\) belongs to \(M_v\). Hence \(R\) is \(M_v\)-alternating and its first and last edges belong to \(M_v\).
Moreover, \[V(C)\cap V(R)=\{p_1\},\] because \(V(C)\cap V(P)=\{p_1\}\) and the vertices \(q_2,q_3,\ldots,q_{w-1}\) lie outside \(V(P)\cup V(C)\). Therefore \(C\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 1.2. Assume that \(u\in V(P)\), say \(u=p_j\) for some odd \(j\), see Figure 4 for the case \(j>i\). Since \(u\neq v\), we have \(i\neq j\). Let \[a:=\min\{i,j\},\qquad b:=\max\{i,j\},\qquad z:=p_b .\] Let \(D\) be the cycle obtained by joining \(Q\) with the \(p_j\)–\(p_i\) subpath of \(P\). Equivalently, \[D= \begin{cases} q_1,q_2,\ldots,q_w,p_{j-1},p_{j-2},\ldots,p_i, & \text{if } i<j,\\[2mm] q_1,q_2,\ldots,q_w,p_{j+1},p_{j+2},\ldots,p_i, & \text{if } j<i. \end{cases}\]
Since \(i\) and \(j\) are odd, the two edges of \(D\) incident with \(z=p_b\) do not belong to \(M_v\), whereas all the remaining edges of \(D\) alternate with respect to \(M_v\). Thus \(D\) is an \(M_v\)-blossom based at \(z\). In particular, \[|E(D)\cap M_v|=\frac{|V(D)|-1}{2}.\]
Since \(b\) is odd and \(t\) is even, the vertex \(p_{b+1}\) exists and \[zp_{b+1}=p_bp_{b+1}\in M_v.\]
The length-one path \[R:=z,p_{b+1},\] is therefore \(M_v\)-alternating and its unique edge belongs to \(M_v\). Also, \(p_{b+1}\notin V(D)\), so \[V(D)\cap V(R)=\{z\}.\]
Hence \(D\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 1.3. Assume that \(u\in V(C)\setminus V(P)\), say \(u=c_j\), see Figure 5. Let \(X\) be the \(u\)–\(p_1\) path in \(C\) whose first edge belongs to \(M_v\). Such a path exists because exactly one of the two edges of \(C\) incident with \(u\) belongs to \(M_v\). Its last edge does not belong to \(M_v\), because both edges of \(C\) incident with \(p_1=c_1\) are outside \(M_v\).
Let \(P[p_1,p_i]\) denote the \(p_1\)–\(p_i\) subpath of \(P\), possibly of length zero if \(i=1\). Consider the cycle \[D:=X\,P[p_1,p_i]\,Q,\] where the paths are concatenated in the natural way. At the vertex \(v=p_i\), the two incident edges of \(D\) do not belong to \(M_v\): one is the first edge \(q_1q_2\) of \(Q\), and the other is either the last edge of \(P[p_1,p_i]\), when \(i>1\), or the last edge of \(X\), when \(i=1\). All other edges of \(D\) alternate with respect to \(M_v\). Hence \(D\) is an \(M_v\)-blossom based at \(v\), and \[|E(D)\cap M_v|=\frac{|V(D)|-1}{2}.\]
The length-one path \[R:=v,M_v(v),\] has its unique edge in \(M_v\). Moreover, \(M_v(v)\notin V(D)\), and hence \[V(D)\cap V(R)=\{v\}.\]
Thus \(D\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 2. Assume that \(v\in V(P)\), say \(v=p_i\) for some even \(i\). Figure 6 illustrates the subcase in which \(u\) also lies on \(P\).
Since \(w\geq 4\), the vertex \(q_3\) is defined and lies outside \(V(P)\cup V(C)\). Consider the path \[R:=p_1,p_2,\ldots,p_i(=q_1),q_2,q_3 .\]
The cycle \(C\) is an \(M_v\)-blossom based at \(p_1=c_1\). The path \(R\) is \(M_v\)-alternating: its first edge \(p_1p_2\) belongs to \(M_v\), the edge \(p_{i-1}p_i\) belongs to \(M_v\) because \(i\) is even, the edge \(q_1q_2\) does not belong to \(M_v\), and the edge \(q_2q_3\) belongs to \(M_v\). Hence the first and last edges of \(R\) belong to \(M_v\).
Furthermore, \[V(C)\cap V(R)=\{p_1\},\] because \(V(C)\cap V(P)=\{p_1\}\) and \(q_2,q_3\notin V(P)\cup V(C)\). Therefore \(C\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 3. Assume that \(v\in V(C)-V(P)\), say \(v=c_{i}\) for some \(i\). According to the position of the vertex \(u\), we consider the following subcases.
Case 3.1. Assume that \(u\in V(P)\), say \(u=p_j\) for some odd \(j\). Let \(Y\) be the \(p_1\)–\(v\) path in \(C\) whose last edge belongs to \(M_v\). Such a path exists because exactly one of the two edges of \(C\) incident with \(v\) belongs to \(M_v\). Its first edge does not belong to \(M_v\), since both edges of \(C\) incident with \(p_1=c_1\) are outside \(M_v\).
Let \(P[u,p_1]\) denote the \(u\)–\(p_1\) subpath of \(P\), possibly of length zero if \(u=p_1\). Consider the cycle \[D:=Y\,Q\,P[u,p_1],\] where the paths are concatenated in the natural way. At the vertex \(u=p_j\), the two incident edges of \(D\) do not belong to \(M_v\): one is the last edge \(q_{w-1}q_w\) of \(Q\), and the other is either the first edge of \(P[u,p_1]\), when \(j>1\), or the first edge of \(Y\), when \(j=1\). All other edges of \(D\) alternate with respect to \(M_v\). Hence \(D\) is an \(M_v\)-blossom based at \(u\), and \[|E(D)\cap M_v|=\frac{|V(D)|-1}{2}.\]
The length-one path \[R:=u,M_v(u),\] has its unique edge in \(M_v\). Moreover, \(M_v(u)\notin V(D)\), and hence \[V(D)\cap V(R)=\{u\}.\]
Therefore \(D\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 3.2. Assume that \(u\in V(P)\), say \(u=p_j\) for some even \(j\), see Figure 7. Consider the path \[R:=p_1,p_2,\ldots,p_j(=q_w),q_{w-1},q_{w-2},\ldots,q_2 .\]
The cycle \(C\) is an \(M_v\)-blossom based at \(p_1=c_1\). Since \(j\) is even, the edge \(p_{j-1}p_j\) belongs to \(M_v\). The next edge \(q_wq_{w-1}\) does not belong to \(M_v\), and the reversed part of \(Q\) alternates with respect to \(M_v\), ending with the edge \(q_3q_2\in M_v\). Therefore \(R\) is \(M_v\)-alternating and its first and last edges belong to \(M_v\).
Moreover, \[V(C)\cap V(R)=\{p_1\},\] because \(q_2,q_3,\ldots,q_{w-1}\) lie outside \(V(P)\cup V(C)\). Hence \(C\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 3.3. Assume that \(u\in V(C)\setminus V(P)\). Then both vertices \(u\) and \(v\) lie in \(V(C)\setminus V(P)\). Write \[v=c_i,\qquad u=c_j .\]
By reversing the cyclic orientation of \(C\), if necessary, we may assume that \[2\leq i<j\leq 2r+1.\]
This does not interchange \(u\) and \(v\); it only fixes the notation along the cycle \(C\). Let \[X:=c_i,c_{i+1},\ldots,c_j .\]
Since \(X\) does not contain the base \(c_1\), it is an \(M_v\)-alternating path. We consider the four possibilities determined by the first and last edges of \(X\).
Case 3.3.1. If the first and last edges of \(X\) belong to \(M_v\), then \[C^*:=q_1,q_2,\ldots,q_w(=c_j),c_{j-1},c_{j-2},\ldots,c_i(=q_1),\] is an even \(M_v\)-alternating cycle, see Figure 8. Therefore \[M:=M_v\triangle E(C^*),\] is again a perfect matching of \(G\).
Now consider the cycle \[D:=c_1,c_2,\ldots,c_i(=q_1),q_2,\ldots,q_w(=c_j), c_{j+1},\ldots,c_{2r+1},c_1,\] where the segment \(c_{j+1},\ldots,c_{2r+1}\) is omitted if \(j=2r+1\). After rotating the matching along \(C^*\), the cycle \(D\) is an \(M\)-blossom based at \(c_1=p_1\). Indeed, the edges of \(Q\) have been switched, the edges of \(C\setminus X\) have not been switched, and the only two consecutive non-\(M\) edges on \(D\) are the two edges incident with \(c_1\). Hence \[|E(D)\cap M|=\frac{|V(D)|-1}{2}.\]
The length-one path \[R:=p_1,p_2,\] has its unique edge in \(M\), and \[V(D)\cap V(R)=\{p_1\}.\]
Therefore \(D\) together with \(R\) is an \(M\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 3.3.2. If neither the first nor the last edge of \(X\) belongs to \(M_v\), then consider the cycle \[D:=c_1,c_2,\ldots,c_i(=q_1),q_2,\ldots,q_w(=c_j), c_{j+1},\ldots,c_{2r+1},c_1,\] where the segment \(c_{j+1},\ldots,c_{2r+1}\) is omitted if \(j=2r+1\). The cycle \(D\) is an \(M_v\)-blossom based at \(c_1=p_1\), see Figure 9. Indeed, the two edges of \(D\) incident with \(c_1\) do not belong to \(M_v\), while all remaining edges alternate with respect to \(M_v\). Hence \[|E(D)\cap M_v|=\frac{|V(D)|-1}{2}.\]
The length-one path \[R:=p_1,p_2,\] has its unique edge in \(M_v\), and \[V(D)\cap V(R)=\{p_1\}.\]
Therefore \(D\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 3.3.3. Assume that the first edge of \(X\) belongs to \(M_v\), and the last edge of \(X\) does not belong to \(M_v\). Consider the cycle \[D:=q_1,q_2,\ldots,q_w(=c_j),c_{j-1},c_{j-2},\ldots,c_i(=q_1).\]
Then \(D\) is an \(M_v\)-blossom based at \(u=c_j\), see Figure 10. Indeed, the last edge \(q_{w-1}q_w\) of \(Q\) and the last edge \(c_{j-1}c_j\) of \(X\) both lie outside \(M_v\), while all remaining edges of \(D\) alternate with respect to \(M_v\). Hence \[|E(D)\cap M_v|=\frac{|V(D)|-1}{2}.\]
Since the last edge of \(X\) does not belong to \(M_v\), the edge \(c_jc_{j+1}=uM_v(u)\) belongs to \(M_v\). Thus the length-one path \[R:=c_j,c_{j+1},\] has its unique edge in \(M_v\), and \[V(D)\cap V(R)=\{c_j\}.\]
Therefore \(D\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
Case 3.3.4. Assume that the first edge of \(X\) does not belong to \(M_v\), and the last edge of \(X\) belongs to \(M_v\). Consider again the cycle \[D:=q_1,q_2,\ldots,q_w(=c_j),c_{j-1},c_{j-2},\ldots,c_i(=q_1).\]
Then \(D\) is an \(M_v\)-blossom based at \(v=c_i\). Indeed, the first edge \(q_1q_2\) of \(Q\) and the first edge \(c_ic_{i+1}\) of \(X\) both lie outside \(M_v\), while all remaining edges of \(D\) alternate with respect to \(M_v\). Hence \[|E(D)\cap M_v|=\frac{|V(D)|-1}{2}.\]
Since the first edge of \(X\) does not belong to \(M_v\), the edge \(c_ic_{i-1}=vM_v(v)\) belongs to \(M_v\). Thus the length-one path \[R:=c_i,c_{i-1},\] has its unique edge in \(M_v\), and \[V(D)\cap V(R)=\{c_i\}.\]
Therefore \(D\) together with \(R\) is an \(M_v\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\).
The four subcases in Case 3.3 exhaust all possibilities for the first and last edges of \(X\). Together with Cases 1, 2, 3.1, and 3.2, this covers all possible positions of \(v\) and \(u\) in \(V(P)\cup V(C)\), without interchanging their roles. In every case we have obtained a perfect matching \(M\) and an \(M\)-perfect flower containing \(x=q_2\). This contradicts \(x\in PFF(G)\). Therefore no such edge \(e\) exists, and \[E(PFF(G),PF(G))\cap E(H)=\emptyset.\] ◻
Then, from Theorem 3.4 we obtain the main result of this work.
Theorem 3.5. Let \(G\) be a Kőnig-Egerváry graph. Then \[\begin{eqnarray*} \det(G) & = & \det\left(G[PF(G)]\right)\det\left(G[PFF(G)]\right),\\ perm(G) & = & perm(G[PF(G)])perm(G[PFF(G)]). \end{eqnarray*}\]
Proof. Set \[G_1:=G[PF(G)] \quad\text{and}\quad G_2:=G[PFF(G)].\]
If \(Sachs(G)=\emptyset\), then by Theorem 3.1, \[\det(G)=0 \quad\text{and}\quad perm(G)=0.\]
Moreover, at least one of the graphs \(G_1\) and \(G_2\) has no Sachs subgraphs. Indeed, if there existed \[H_1\in Sachs{G_1} \quad\text{and}\quad H_2\in Sachs{G_2},\] then \(H_1\cup H_2\) would be a Sachs subgraph of \(G\), a contradiction. Hence at least one of \(\det(G_1),\det(G_2)\) is zero, and at least one of \(perm(G_1),perm(G_2)\) is zero. Therefore, \[\det(G)=\det(G_1)\det(G_2) \quad\text{and}\quad perm(G)=perm(G_1)perm(G_2).\]
Assume now that \(Sachs(G)\neq\emptyset\). Since every Sachs subgraph is spanning, we have \(prk(G)=|G|\). Thus, by Corollary 3.3, \[|G|=prk(G)=2\mu(G),\] and therefore \(G\) has a perfect matching.
Let \(H\in Sachs(G)\). By Theorem 3.4, \[E(PF(G),PFF(G))\cap E(H)=\emptyset.\]
Hence every connected component of \(H\) lies entirely in \(PF(G)\) or entirely in \(PFF(G)\). Therefore \[H=H_1\cup H_2,\] where \[H_1:=H[PF(G)] \quad\text{and}\quad H_2:=H[PFF(G)].\]
Clearly, \[H_1\in Sachs{G_1} \quad\text{and}\quad H_2\in Sachs{G_2}.\]
Conversely, if \[H_1\in Sachs{G_1} \quad\text{and}\quad H_2\in Sachs{G_2},\] then \(H_1\cup H_2\in Sachs(G)\). Thus \[H\mapsto (H_1,H_2),\] is a bijection between \(Sachs(G)\) and \(Sachs{G_1}\times Sachs{G_2}\).
Since the connected components of \(H\) are precisely the connected components of \(H_1\) together with those of \(H_2\), we have \[k(H)=k(H_1)+k(H_2) \quad\text{and}\quad m(H)=m(H_1)+m(H_2).\]
Hence \[\begin{eqnarray*} (-1)^{k(H)}2^{m(H)} &=& (-1)^{k(H_1)+k(H_2)}2^{m(H_1)+m(H_2)} \\ &=& (-1)^{k(H_1)}2^{m(H_1)} (-1)^{k(H_2)}2^{m(H_2)}, \end{eqnarray*}\] and also \[2^{m(H)}=2^{m(H_1)}2^{m(H_2)}.\]
Using Theorem 3.1 and the above bijection, we obtain \[\begin{eqnarray*} \det(G) &=& \sum_{H\in Sachs(G)}(-1)^{k(H)}2^{m(H)} \\ &=& \sum_{H_1\in Sachs{G_1}} \sum_{H_2\in Sachs{G_2}} (-1)^{k(H_1)}2^{m(H_1)} (-1)^{k(H_2)}2^{m(H_2)} \\ &=& \left( \sum_{H_1\in Sachs{G_1}} (-1)^{k(H_1)}2^{m(H_1)} \right) \left( \sum_{H_2\in Sachs{G_2}} (-1)^{k(H_2)}2^{m(H_2)} \right) \\ &=& \det(G_1)\det(G_2). \end{eqnarray*}\]
Similarly, \[\begin{eqnarray*} perm(G) &=& \sum_{H\in Sachs(G)}2^{m(H)} \\ &=& \sum_{H_1\in Sachs{G_1}} \sum_{H_2\in Sachs{G_2}} 2^{m(H_1)}2^{m(H_2)} \\ &=& \left( \sum_{H_1\in Sachs{G_1}}2^{m(H_1)} \right) \left( \sum_{H_2\in Sachs{G_2}}2^{m(H_2)} \right) \\ &=& perm(G_1)perm(G_2). \end{eqnarray*}\] ◻
By Lemma 3.2 and Theorem 3.4, one has the additivity of \(\mu(G)\) according to the perfect flower decomposition.
Corollary 3.6. Let \(G\) be a Kőnig-Egerváry graph with a perfect matching. Then \[\mu(G)=\mu(G[PF(G)])+\mu(G[PFF(G)]).\]
Proof. Let \(M_1\) and \(M_2\) be maximum matchings of \(G[PF(G)]\) and \(G[PFF(G)]\), respectively. Since \(PF(G)\) and \(PFF(G)\) are disjoint, \(M_1\cup M_2\) is a matching of \(G\). Hence \[\mu(G)\geq \mu(G[PF(G)])+\mu(G[PFF(G)]).\]
On the other hand, let \(M\) be a perfect matching of \(G\). Since \(G[M]\in Sachs(G)\), Theorem 3.4 yields \[E(PF(G),PFF(G))\cap M=\emptyset.\]
Therefore, \[M=\bigl(M\cap E(G[PF(G)])\bigr)\cup \bigl(M\cap E(G[PFF(G)])\bigr),\] and so \[\mu(G)=|M| \leq \mu(G[PF(G)])+\mu(G[PFF(G)]).\]
Thus, \[\mu(G)=\mu(G[PF(G)])+\mu(G[PFF(G)]).\] ◻
To illustrate Theorem 3.5, consider the graph in Figure 11. Here one has \(\det\left(G[PFF(G)]\right)=-4\), while \(\det\left(G[PF(G)]\right)=9\), therefore, by Theorem 3.5, it follows that \[\det\left(G\right)=-4\cdot9=-36.\]
Therefore, by Theorem 3.5, studying when a Kőnig-Egerváry graph is unimodular reduces to studying when the graphs \(G[PFF(G)]\) and \(G[PF(G)]\) are unimodular. This motivates the following problems.
It is known that every Kőnig-Egerváry graph with a unique matching is unimodular; however, the converse is not true. Indeed, unimodularity is only enough to guarantee the existence of a perfect matching. For example, this occurs in the graph obtained by considering two cycles \(C_{4}\) with one common edge. Consequently, the study of unimodularity in Kőnig–Egerváry graphs can be reduced to the analysis of the following two problems. When \(G\) is a Kőnig-Egerváry graph with a perfect matching, then by Theorem 1.1, both graphs \[G[PF(G)],\qquad G[PFF(G)],\] also have a perfect matching and are both Kőnig-Egerváry graphs, so the most natural thing in this context is to study the following.
Problem 4.1.Characterize the unimodular Kőnig-Egerváry graphs \(G\) such that \(G[PF(G)]=G\).
Problem 4.2. Characterize unimodular perfect-flower-free Kőnig-Egerváry graphs, that is, graphs \(G\) such that \(G[PFF(G)]=G\).
During the preparation of this work the authors used ChatGPT-3.5 in order to improve the grammar of several paragraphs of the text. After using this service, the authors reviewed and edited the content as needed and take full responsibility for the content of the publication.