Large odd induced subgraphs via odd cuts

Abstract

Gallai proved that every graph can be partitioned into two sets, each inducing a subgraph with all degrees even. We show that if a graph admits a bipartition in which every vertex has an odd number of neighbors in the opposite part, then it can be partitioned into two sets, each inducing a subgraph with all degrees odd. Consequently, every $n$-vertex graph without isolated vertices has an induced subgraph with all degrees odd on at least $n/5$ vertices, substantially improving the previously known universal lower bound.

Disclosure

“etween 1/5 and 2/7. Determining its exact value remains open. More broadly, the odd-cut viewpoint may be useful in parity problems where cross-degrees are easier to control than degrees within induced subgraphs. Declaration on the Use of Generative AI The author used ChatGPT (OpenAI) for language polishing, structural organization, and im- proving the exposition of some proofs. All mathematical arguments and proofs were indepen- dently checked and finalized by the author, who takes full”

PDF page 4

Classification

Rewriting existing author-written text

Multiplier

4

Verified

2026-08-23T19:06:11.390552Z

Structural counts