pith. sign in

arxiv: 2604.25055 · v1 · submitted 2026-04-27 · 🧮 math.CO

On the Determinant of KH{o}nig-Egerv\'ary Graphs

Kevin Pereyra This is my paper

Pith reviewed 2026-05-08 02:12 UTC · model grok-4.3

classification 🧮 math.CO
keywords Kőnig-Egerváry graphsadjacency matrix determinantgraph decompositionunimodularityperfect matchingscritical independent setsSterboul-Deming configurations
0
0 comments X

The pith

Kőnig-Egerváry graphs factor their adjacency determinants into the product over perfect-flower and perfect-flower-free induced subgraphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a determinant factorization for the adjacency matrices of Kőnig-Egerváry graphs. It shows that for any such graph G the determinant of G equals the product of the determinants of the induced subgraphs on its perfect-flower vertex set and its perfect-flower-free vertex set. The result extends to the permanent as well. A reader would care because the factorization separates the graph into two induced subgraphs with very different structures, one linked to perfect matchings and Sterboul-Deming configurations and the other to critical independent sets, thereby simplifying the analysis of when these graphs are unimodular.

Core claim

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 a very different nature: the graph G[PF(G)], whose structure is closely related to Sterboul--Deming configurations with perfect matching, and the graph G[PFF(G)], which is governed by the theory of critical independent sets. In this way, the paper gives a new structural framework for the study of unimodular graphs through K

What carries the argument

The partition of the vertex set into the perfect-flower part PF(G) and the perfect-flower-free part PFF(G), which induces a factorization of the adjacency matrix determinant as a product over the two corresponding induced subgraphs.

If this is right

  • The study of unimodularity for Kőnig-Egerváry graphs reduces to separate checks on the two induced subgraphs.
  • The permanent of the adjacency matrix factors in exactly the same way over the partition.
  • The perfect-flower part connects directly to Sterboul-Deming configurations that admit perfect matchings.
  • The perfect-flower-free part is analyzed using the existing theory of critical independent sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same partition might be used to factor other matrix invariants such as the characteristic polynomial or the number of spanning trees.
  • Combining this decomposition with existing ones such as the SD-KE decomposition could yield further reductions for determinant calculations.
  • Explicit algorithms to compute the perfect-flower and perfect-flower-free parts would allow direct verification on families of Kőnig-Egerváry graphs.

Load-bearing premise

The perfect-flower and perfect-flower-free parts induce subgraphs whose adjacency matrices combine without cross terms that would prevent the determinant from factoring exactly as stated.

What would settle it

A concrete Kőnig-Egerváry graph where the determinant of the full adjacency matrix is not equal to the product of the determinants on the induced subgraphs on its perfect-flower part and perfect-flower-free part.

Figures

Figures reproduced from arXiv: 2604.25055 by Kevin Pereyra.

Figure 1
Figure 1. Figure 1: The partition into P F(G) and P F F(G), and a Sachs subgraph crossing the partition. Moreover, note that G satisfies: µ(G) + α(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) = Sachsprk(G). This reduces the study of the determinant/permanent of the graph via The￾orem 3.1 to the study of Kőnig-Egerváry … view at source ↗
Figure 2
Figure 2. Figure 2: An edge between P F(G) and P F F(G), and an Mv-perfect flower containing v. Then note that the edges vMv(v) and vx are distinct. Set S := V (P) ∪ V (C). Since (P, C) is an Mv-perfect flower, every vertex of S is matched by Mv to another vertex of S. In particular, no edge of Mv has exactly one endpoint in S. By Theorem 2.1, the connected component K of view at source ↗
Figure 3
Figure 3. Figure 3: Case 1.1: both vertices lie on P. Case 1.2. Assume that u ∈ V (P), say u = pj for some odd j, see view at source ↗
Figure 4
Figure 4. Figure 4: Case 1.2: both vertices lie on P. Case 1.3. Assume that u ∈ V (C) \ V (P), say u = cj , see view at source ↗
Figure 5
Figure 5. Figure 5: Case 1.3: one vertex lies on P and the other on C. Case 2. Assume that v ∈ V (P), say v = pi for some even i view at source ↗
Figure 6
Figure 6. Figure 6: Case 2: v lies on P at an even position; the drawing shows the subcase in which u also lies on P. 14 view at source ↗
Figure 7
Figure 7. Figure 7: Case 3.2: one vertex lies on C − V (P) and the other on P. Case 3.3. Assume that u ∈ V (C) \ V (P). Then both vertices u and v lie in V (C) \ V (P). Write v = ci , u = cj . By reversing the cyclic orientation of C, if necessary, we may assume that 2 ≤ i < j ≤ 2r + 1. This does not interchange u and v; it only fixes the notation along the cycle C. Let X := ci , ci+1, . . . , cj . Since X does not contain th… view at source ↗
Figure 8
Figure 8. Figure 8: Case 3.3.1: rotating the matching on the alternating cycle. view at source ↗
Figure 9
Figure 9. Figure 9: Case 3.3.2: both end edges of X are outside Mv. Case 3.3.3. Assume that the first edge of X belongs to Mv, and the last edge of X does not belong to Mv. Consider the cycle D := q1, q2, . . . , qw(= cj ), cj−1, cj−2, . . . , ci(= q1). Then D is an Mv-blossom based at u = cj , see view at source ↗
Figure 10
Figure 10. Figure 10: Case 3.3.3: the first edge of X belongs to Mv, but the last does not. 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) ∪ V (C), without interchanging their roles. In 19 view at source ↗
Figure 11
Figure 11. Figure 11: An example illustrating the determinant factorization via view at source ↗
read the original abstract

Several graph decompositions that factorize the determinant of the adjacency matrix isolate a K\H{o}nig-Egerv\'ary 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\H{o}nig-Egerv\'ary graphs. In this paper we advance this point of view by introducing a new determinant factorization inside the class of K\H{o}nig-Egerv\'ary graphs. More precisely, given a K\H{o}nig-Egerv\'ary 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 a very different nature: the graph $G[PF(G)]$, whose structure is closely related to Sterboul--Deming configurations with perfect matching, and the graph $G[PFF(G)]$, which is governed by the theory of critical independent sets. In this way, the paper gives a new structural framework for the study of unimodular graphs through K\H{o}nig-Egerv\'ary theory.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper introduces the perfect-flower part PF(G) and perfect-flower-free part PFF(G) as a partition of the vertices of any König-Egerváry graph G. It proves that the determinant of the adjacency matrix of G factors exactly as det(G) = det(G[PF(G)]) det(G[PFF(G)]), and obtains the analogous factorization for the permanent. The decomposition is presented as a new structural tool that reduces questions about unimodularity in KE graphs to two induced subgraphs of distinct types: one linked to Sterboul-Deming configurations with perfect matchings and the other governed by critical independent sets.

Significance. If the factorization is valid, the result supplies a concrete reduction for the study of determinants and permanents within the class of König-Egerváry graphs, complementing the SD-KE and critical-independence decompositions already in the literature. The separation into subgraphs with qualitatively different combinatorial descriptions offers a new framework for attacking unimodularity questions. The paper also establishes the parallel statement for the permanent, which strengthens its utility.

major comments (1)
  1. [Main theorem (abstract and §3)] The claimed equality det(A_G) = det(A_{PF}) det(A_{PFF}) for the adjacency matrix A_G holds if and only if A_G is block-diagonal with respect to the partition (PF(G), PFF(G)), i.e., the off-diagonal blocks are identically zero. The definitions of PF(G) (tied to Sterboul-Deming configurations) and PFF(G) (tied to critical independent sets) must be shown to guarantee the absence of edges between the two parts; otherwise the general block-determinant formula introduces Schur-complement terms that prevent exact factorization. This verification is load-bearing for the main theorem stated in the abstract and must appear explicitly in the proof.
minor comments (2)
  1. [Introduction] Clarify at first use that det(G) denotes the determinant of the adjacency matrix of G (rather than the Laplacian or another matrix).
  2. [Abstract] The abstract mentions that the result 'advances this point of view' but does not cite the specific prior decompositions (SD-KE and Larson's critical independence) by equation or theorem number; adding those references would help readers locate the context.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying a key detail that requires explicit verification in the proof of the main theorem. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [Main theorem (abstract and §3)] The claimed equality det(A_G) = det(A_{PF}) det(A_{PFF}) for the adjacency matrix A_G holds if and only if A_G is block-diagonal with respect to the partition (PF(G), PFF(G)), i.e., the off-diagonal blocks are identically zero. The definitions of PF(G) (tied to Sterboul-Deming configurations) and PFF(G) (tied to critical independent sets) must be shown to guarantee the absence of edges between the two parts; otherwise the general block-determinant formula introduces Schur-complement terms that prevent exact factorization. This verification is load-bearing for the main theorem stated in the abstract and must appear explicitly in the proof.

    Authors: We agree that the exact factorization requires the adjacency matrix of G to be block-diagonal with respect to the partition (PF(G), PFF(G)), i.e., that no edges exist between the two sets. The definitions ensure this separation: PF(G) is the union of all vertices that participate in Sterboul-Deming configurations admitting a perfect matching, while PFF(G) is the complement consisting of vertices governed by maximal critical independent sets. In a König-Egerváry graph, the presence of any cross edge would increase either the matching number or the independence number in a way that violates the equality α(G) + ν(G) = |V(G)|. We will insert a short lemma immediately before the main theorem in §3 that proves the absence of cross edges by contradiction, using the perfect-matching property inside each flower and the criticality of the independent sets in PFF(G). This lemma will be self-contained and will make the block-diagonal structure explicit, thereby completing the proof of the factorization. revision: yes

Circularity Check

0 steps flagged

No circularity: direct structural proof of factorization

full rationale

The paper defines the PF(G) and PFF(G) partition for König-Egerváry graphs and states a theorem that det(G) factors as the product of the induced determinants on those parts. The abstract and claim present this as a new result obtained by analyzing the structure (Sterboul-Deming configurations and critical independent sets), without any equation or definition that makes the factorization hold tautologically by construction. No self-citation is used as the load-bearing justification for the key step, and the derivation does not rename a known result or smuggle an ansatz. The result is therefore self-contained as a proof within the given graph class.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 2 invented entities

The theorem rests on the established definition of Kőnig-Egerváry graphs and standard linear-algebra facts about determinants; the new partition is introduced to enable the factorization.

axioms (2)
  • standard math Determinant and permanent are multiplicative over block-diagonal matrices (or equivalent block structure after vertex ordering).
    Invoked to obtain the product formula once the adjacency matrix is shown to respect the PF/PFF partition.
  • domain assumption Kőnig-Egerváry graphs admit the stated partition into perfect-flower and perfect-flower-free induced subgraphs.
    The partition is defined within the paper for this class; the result holds conditionally on that definition.
invented entities (2)
  • Perfect-flower part PF(G) no independent evidence
    purpose: Isolate the subgraph whose structure is governed by Sterboul-Deming configurations with perfect matchings.
    Newly defined partition component; no independent existence outside the paper's construction.
  • Perfect-flower-free part PFF(G) no independent evidence
    purpose: Isolate the complementary subgraph governed by critical independent sets.
    Newly defined partition component; no independent existence outside the paper's construction.

pith-pipeline@v0.9.0 · 5577 in / 1476 out tokens · 46802 ms · 2026-05-08T02:12:34.748400+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages

  1. [1]

    C., Durán, G., Faria, L., Grippo, L

    Bonomo, F., Dourado, M. C., Durán, G., Faria, L., Grippo, L. N., and Safe, M. D. (2013). Forbidden subgraphs and the könig–egerváry property. Discrete Applied Mathematics, 161(16-17):2380–2388. 2

    work page 2013

  2. [2]

    L., and Simeone, B

    Bourjolly, J.-M., Hammer, P. L., and Simeone, B. (2009). Node-weighted graphs having the könig-egervary property. InMathematical Programming at Oberwolfach II, pages 44–63. Springer. 2

    work page 2009

  3. [3]

    Deming, R. W. (1979). Independence numbers of graphs-an extension of the könig-egerváry theorem.Discrete Mathematics, 27(1):23–33. 2

    work page 1979

  4. [4]

    (2012).Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics

    Diestel, R. (2012).Graph Theory, 4th Edition, volume 173 ofGraduate texts in mathematics. Springer. 5 24

    work page 2012

  5. [5]

    Edmonds, J. (1965). Paths, trees, and flowers.Canadian Journal of mathematics, 17:449–467. 2

    work page 1965

  6. [6]

    (1931).On combinatorial properties of matrices

    Egerváry, E. (1931).On combinatorial properties of matrices. 2

    work page 1931

  7. [7]

    Gavril, F. (1977). Testing for equality between maximum matching and minimum node covering.Information processing letters, 6(6):199–202. 2

    work page 1977

  8. [8]

    Harary, F. (1962). The determinant of the adjacency matrix of a graph. Siam Review, 4(3):202–210. 6, 7

    work page 1962

  9. [9]

    E., and Mandrescu, E

    Jarden, A., Levit, V. E., and Mandrescu, E. (2017). Two more characteri- zations of könig–egerváry graphs.Discrete Applied Mathematics, 231:175–

    work page 2017

  10. [10]

    A., Levit, V

    Jaume, D. A., Levit, V. E., Mandrescu, E., Molina, G., and Pereyra, K. (2025a). On the könig–egerváry index of a graph.Available at SSRN 5404413. 2

    work page

  11. [11]

    A., Martinez, D

    Jaume, D. A., Martinez, D. G., Panelo, C., and Pereyra, K. (2025b). Generalized Edmonds-Sterboul-Deming configurations. part 3: Determi- nantal multiplicativity of the SD–KE decomposition of matchable graphs. Submitted. 2

    work page

  12. [12]

    A., Martinez, D

    Jaume, D. A., Martinez, D. G., Panelo, C., and Pereyra, K. (2026). Towards a structural characterization of unimodular graphs with a unique perfect matching.Discrete Mathematics, 349(8):115062. 3, 4

    work page 2026

  13. [13]

    Jaume, D. A. and Molina, G. (2025). Generalized Edmonds-Sterboul- Demingconfigurationspart2: SD–KEdecompositionofgraphs.Submitted. 2

    work page 2025

  14. [14]

    A., Panelo, C., and Pereyra, K

    Jaume, D. A., Panelo, C., and Pereyra, K. (2025c). General- ized Edmonds-Sterboul-Deming configurations. Part 1: Sterboul-Deming graphs .Submitted. 2, 3

    work page

  15. [15]

    Korach, E., Nguyen, T., and Peis, B. (2006). Subgraph characterization of red/blue-split graph and könig egerváry graphs. InSODA, pages 842–

    work page 2006

  16. [16]

    Larson, C. E. (2011). The critical independence number and an indepen- dence decomposition.European Journal of Combinatorics, 32(2):294–300. 3, 4

    work page 2011

  17. [17]

    Levit, V. E. and Mandrescu, E. (2006). Onα-critical edges in könig– egervary graphs.Discrete Mathematics, 306(15):1684–1693. 2

    work page 2006

  18. [18]

    Levit, V. E. and Mandrescu, E. (2012). Critical independent sets and könig–egerváry graphs.Graphs and Combinatorics, 28(2):243–250. 2

    work page 2012

  19. [19]

    R., and Watkins, W

    Merris, R., Rebman, K. R., and Watkins, W. (1981). Permanental poly- nomials of graphs.Linear Algebra and Its Applications, 38:273–288. 7

    work page 1981

  20. [20]

    Panelo, C. (2026). Toward the structural characterization of unimodular graphs with a unique perfect matching (II).Submitted. 3

    work page 2026

  21. [21]

    Pereyra, K. (2025a). Determinant factorization via the SD-KE decom- position in general graphs.Submitted. 3

    work page

  22. [22]

    Pereyra, K. (2025b). ker(G) =core(G)via Forbidden Subgraphs.Sub- mitted. 4

    work page

  23. [23]

    Pereyra, K. (2025c). Sterboul-deming graphs: Characterizations.Sub- mitted. 3

    work page

  24. [24]

    Pereyra, K. (2026). Unimodularity inC4k-free Graphs.submitted. 7

    work page 2026

  25. [25]

    Plummer, M. D. and Lovász, L. (1986).Matching theory, volume 29. Elsevier. 5

    work page 1986

  26. [26]

    Pulleyblank, W. R. (1979). Minimum node covers and 2-bicritical graphs.Mathematical programming, 17(1):91–103. 3

    work page 1979

  27. [27]

    Sachs, H. (2022). Beziehungen zwischen den in einem graphen enthalte- nen kreisen und seinem charakteristischen polynom.Publicationes Mathe- maticae Debrecen, 11(1-4):119–134. 6

    work page 2022

  28. [28]

    Sterboul, F. (1979). A characterization of the graphs in which the transversal number equals the matching number.Journal of Combina- torial Theory, Series B, 27(2):228–229. 2 26

    work page 1979