Matching cut and girth

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite simple graph $G=(V,E)$, a matching is an edge set whose edges have pairwise disjoint endpoints. A matching cut is a set $\delta_G(S)=\{uv\in E:u\in S,v\in V\setminus S\}$ that is a matching, where $\varnothing\ne S\ne V$. The average degree is $2|E|/|V|$, and the girth is the length of a shortest cycle, taken to be $+\infty$ for forests.

Statement recorded in the supplied source.

For every positive real $d$, does there exist an integer $g$ such that every graph $G$ with at least two vertices, average degree less than $d$, and girth at least $g$ has a matching cut? [S2]

Short English statement

Does sufficiently large girth force a matching cut when the average degree has a fixed upper bound?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 3120 (OPG-37364). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Open Problem Garden, Matching cut and girth, original node 37364, statement and mathematical discussion. https://www.openproblemgarden.org/op/matching_cut_and_girth.