One-to-one correspondence between even spanning subgraphs and spanning subgraphs given parity of each vertex’s degree

combinatoricsgraph theory

Given any connected graph $G = (V, E)$, the number of even spanning subgraphs is $2^{|E|-|V|+1}$. One nice proof of this fact is given here.

Recently, I came to know that the number of spanning subgraphs where we are given the parity of the degrees of each vertex of the subgraph is also $2^{|E|-|V|+1}$, provided that the number of odd vertices is even. Thus as a method of proving the fact, I wanted to show that there exists a one-to-one correspondence between them and the even spanning subgraphs of $G$.

However, I was only able to prove this when $G$ is a complete graph. If so, let us say that the odd vertices are $a_1, a_2, … a_{2k}$ in some order. Consider the spanning subgraph $H = (V, E')$, where $E' = \{a_{2i-1}a_{2i}|1 \leq i \leq k\}$. Then, we can establish a one-to-one correspondence between any even spanning subgraph $H'$ to $H+H'$. (Here $H+H'$ refers to the graph with edge set the symmetric difference of edge sets of $H$ and $H'$, as in the link).

This proof may work for more general graphs, but it entirely breaks down if say the set of odd vertices form an indpendent set, as then no edge of $H'$ actually belongs to $G$. So how can I show this correspondence for any connected graph in general?

Best Answer

The same idea still works. If $H$ is a fixed solution to the spanning-subgraph-given-parity problem, and $H'$ is any even spanning subgraph, then $H + H'$ will have the same parity, and so it will be another solution. Moreover, this will give you all the solutions, because the symmetric difference of two solutions is an even graph.

The only question is, how can we find an initial solution? To do this:

  • Pair up the $2k$ odd vertices into $k$ pairs, so that each pair is in the same connected component of $G$. (If this is not possible, then no solution $H$ exists, because each component of $H$ must have an even number of odd vertices.)
  • For $1 \le i \le k$, let $P_i$ be a path in $G$ joining the $i^{\text{th}}$ pair of vertices.
  • Let $H$ be the symmetric difference $P_1 + P_2 + \dots + P_k$.

This subgraph $H$ will have the degree parities you want, because $P_i$ has an even degree on all vertices except the $i^{\text{th}}$ pair of odd vertices.

Related Question