Exact Cuts and a Simple Proof of the Zero Graphs Theorem

Abstract

Let $G$ be a simple graph on $n$ vertices and an even number of edges. It was proved in [15] that the zero-sum (mod 2) Ramsey numbers are given by

$$R(G,{\mathbb{Z}}_2)=\{\begin{array}{ll}n+2& \text{if }G=K_n,n\equiv 0,1(\mathrm{mod}4)\\ n+1& \text{if }G=K_p\cup K_q(\frac{p}{2})+(\frac{q}{2})\equiv 0(\mathrm{mod}2)\\ n+1& \text{if all degrees in }G\text{ are odd}\\ n& \text{otherwise}\end{array}$$

The proof is rather long and based on complicated algebraic machinery. Here we shall prove that $R(G,{\mathbb{Z}}_2)\le n+2$ with equality holding iff $G=K_{n,}n\equiv 0,1(\mathrm{mod}4)$.

The proof uses simple combinatorial arguments and it is also applied to the case, not considered before, when $G$ has an odd number of edges. Some algorithmic aspects, which cannot be tackled using the methods of [1] and [15], are also considered.