×

Simple proofs to three parity theorems. (English) Zbl 0852.05067

The author presents new proofs of the following parity theorems:
1. (Gallai) Let \(G\) be a graph. Then there exists a partition \((A, B)\) of its vertex set \(V(G)\) such that in the induced subgraphs \(G[A]\) and \(G[B]\) with vertex sets \(A\) and \(B\) respectively, all degrees are even. Moreover, there exists a partition \((C, D)\) of \(V(G)\) such that in \(G[C]\), all degrees are even and in \(C[D]\), all degree are odd.
2. (Sutner) Each graph \(G\) has an odd parity cover, i.e. there exists a subset \(Q\subseteq V(G)\) such that for each vertex \(v\) of \(G\), the cardinality of \(\overline N(v)\cap Q\) is odd, where \(\overline N(v)\) denotes the set of all neighbours of \(v\) including \(v\) itself.
3. (Manber, Shao) A graph \(G\) has the odd cycle property (i.e. there exists a subset \(Q\subseteq E(G)\) such that for each cycle \(C\) of \(G\), the cardinality of \(E(C)\cap Q\) is odd) iff every block in \(G\) is a cycle or an edge.
In these new proofs, linear algebra over the Galois field \(\text{GF}(2)\) is used, especially the following result: If \(B\) is a matrix over \(\text{GF}(2)\), then there is no vector \(\vec x\) with \[ B\vec x= \begin{pmatrix} 1\\ 1\\ \vdots\\ 1\end{pmatrix} \] iff there exists an odd number of row vectors in \(B\) whose sum is the zero vector. The author also generalizes the above-mentioned theorem of Manber and Shao to binary matroids.
Reviewer: A.Huck (Hannover)

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles
05C65 Hypergraphs
05B35 Combinatorial aspects of matroids and geometric lattices
PDFBibTeX XMLCite