Crossing pairs for a graph cut
Definitionopg37364_cut_pairsgraph-theorymatching-cuts
Let be a simple graph on a vertex set , and let . The crossing-pair set is
Every undirected edge crossing the cut is represented once, oriented from to its complement. This provides a shared counting interface for the expansion-to-immunity step in the proof of Lemma 5. The definition imposes no expansion or graph-existence assertion.
Definition code
import Definitions.Def_opg37364_matching_cuts
set_option autoImplicit false
namespace OPG37364
universe u
/-- Crossing pairs oriented from the chosen shore into its complement. -/
def cutPairs {V : Type u} (G : SimpleGraph V) (A : Set V) : Set (V × V) :=
{e | e.1 ∈ A ∧ e.2 ∉ A ∧ G.Adj e.1 e.2}
end OPG37364
Source
Crossing-edge notation for the expansion argument in the proof of Lemma 5, Feghali--Lucke--Paulusma--Ries, Matching Cuts in Graphs of High Girth and H-Free Graphs, Algorithmica 87 (2025), 1199--1221, https://doi.org/10.1007/s00453-025-01318-8; uses the existing Prove2Me matching-cut definition ab3f2eb8-d49e-4e0f-ba12-2055a9430b33.