Strict expansion of small cuts implies immunity
ProvedOPG37364.not_hasMatchingCut_of_smallCut_expansionexpansiongraph-theorymatching-cuts
Let be a finite simple graph on . Suppose that every nonempty proper shore satisfying has strictly more crossing edges than vertices:
Then has no matching cut, where a matching cut is a bipartition into nonempty shores with at most one crossing neighbor at each vertex.
This is the elementary expansion-to-immunity implication used in Observation 2 and Lemma 5 of the cited paper. No regularity, bipartiteness, connectedness, girth, or spectral assumptions are required.
Preamble
import Definitions.Def_opg37364_cut_pairs set_option autoImplicit false
Formal statement
namespace OPG37364
universe u
theorem not_hasMatchingCut_of_smallCut_expansion {V : Type u} {G : SimpleGraph V} [Finite V]
(hExpansion : ∀ S : Set V, S.Nonempty → Sᶜ.Nonempty →
S.encard ≤ Sᶜ.encard → S.encard < (cutPairs G S).encard) :
¬ HasMatchingCut G := by sorry
end OPG37364Source
Feghali--Lucke--Paulusma--Ries, Matching Cuts in Graphs of High Girth and H-Free Graphs, Algorithmica 87 (2025), 1199--1221, https://link.springer.com/article/10.1007/s00453-025-01318-8, Observation 2 (matching-cut case) and its use in the proof of Lemma 5; crossing-pair cardinality formulation of that elementary implication.