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{cases}
n+2 & \text{if } G = K_{n}, n \equiv 0,1 \pmod{4} \\
n+1 & \text{if } G = K_{p} \cup K_q({\frac{p}{2}}) + (\frac{q}{2}) \equiv 0 \pmod{2} \\
n+1 & \text{if all degrees in } G \text{ are odd} \\
n & \text{otherwise}
\end{cases}
\]

The proof is rather long and based on complicated algebraic machinery. Here we shall prove that \(R(G,\mathbb{Z}_2) \leq n+2\) with equality holding iff \(G = K_{n,}n \equiv 0,1 \pmod{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.