7
$\begingroup$

An even graph is a graph all of whose vertices have even degree.

A spanning subgraph $H$ of $G$, denoted by $H \subseteq_{sp} G$, is a graph obtained by $G$ by deleting only edges of $G$.

I want to show that if $G$ is a connected graph, then $\big|\{H \subseteq_{sp} G | H$ $is$ $even\}\big| = 2^{e-n+1}$, where $e$ is the number of edges and $n$ the number of vertices of $G$.

Can anyone give me a solution or a hint? Thanks in advance!

$\endgroup$
4
$\begingroup$

Pick a base vertex $v$. For any other vertex $w$, pick a path $P(v,w)$ from $v$ to $w$. $P(v,w)$ exists because $G$ is connected.

For a spanning subgraph $H\subseteq_{sp} G$, we speak of "flipping an edge $e$" to mean removing $e$ from $H$ if $e\in H$, and adding $e$ to $H$ if $e$ is not in $H$. This transformation yields another spanning subgraph. Note that flipping all edges along a path changes the degree of the end vertices of the path by one (provided the path is not a loop), but not any other vertices.

Define an equivalence relation $\sim$ on the set of all spanning subgraphs of $G$ as follows: $H_1\sim H_2$ if $H_2$ is obtained from $H_1$ by flipping all the edges along the path $P(v,w)$ for some $w$. Thus each equivalence class contains $2^{n-1}$ spanning subgraphs, as we have $n-1$ paths $P(v,w)$ to flip.

For any spanning subgraph $H$, there is a unique equivalent graph with even degree for all vertices $w\neq v$ (just flip all paths $P(v,w)$ for which $w$ has odd degree). Call this equivalent subgraph $H'$. In $H'$, $v$ must also have even degree, because the sum of degrees for all vertices is even (being equal to $2\times\text{number of edges}$), and the sum of degrees of all vertices $w\neq v$ is also even by hypothesis. Hence, each equivalence class has a unique even spanning subgraph.

There are $2^e$ spanning subgraphs, and thus $2^{e-n+1}$ equivalence classes, and thus $2^{e-n+1}$ even spanning subgraphs.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ This is a beautiful proof, thank you very much! $\endgroup$ – Ilefen Dec 20 '17 at 23:45
2
$\begingroup$

Let $v_1, \cdots, v_n$ be the vertices of the graph. Fixing the number of vertices, let us do induction on $e$, the number of edges.

Since $G$ is connected, The base case is $e = n-1$, which happens when $G$ is a tree. If $H \subseteq_{sp}G$ is even and contains at least one edge, then $H$ contains a cycle, but a tree can have no cycle, this is impossible. So the only even spanning subgraph is the trivial one, i.e., with $n$ vertices and no edges. So $|\{H\subseteq_{sp}G|H \mbox{ is even}\}| = 1$.

Suppose the assertion holds when $e = m \geq n-1$. Now suppose that $G$ is a connected graph with $m+1$ edges. Let $G'$ be a connected graph obtained by removing an edge $e_0 = v_1v_2$ from $G$. By induction hypothesis $|\{H\subseteq_{sp}G'|H \mbox{ is even}\}| = 2^{m-n+1}$.

How many even spanning subgraoh are there in $G$? There are $2^{m-n+1}$ of them which does not contain $e_0$, and $2^{m-n+1}$ of them containing $e_0$. To see this, let $v_1v_{a_1}v_{a_2}\cdots v_{a_{n-1}}v_2$ be a simple path (no repeated vertices) from $v_1$ to $v_2$. This must exists because $G'$ is connected. Let $\tilde H$ be a even spanning subgraph of $G$ with edges $e_0, v_1v_{a_1}, v_{a_1}v_{a_2}, \cdots, v_{a_{n-1}}v_2$. Then you can show that the following exhausts all even spanning subgraphs containing $e_0$:

$$ \{\tilde H \oplus H \ | \ H \subseteq_{sp} G', H \mbox{ is even} \}, $$

where $H_1 \oplus H_2$ means the "exclusive or" of $H_1$ and $H_2$, that is, the spanning subgraph whose edges are those which appears exactly once in $H_1$ and $H_2$.

This completes the sketch of the proof.

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Well, since $\tilde H$ is actually a cycle, it itself is an even spanning subgraph. And observe that if $H_1$ and $H_2$ are both even spanning subgraphs, so is $H_1 \oplus H_2$. Therefore, you can try to say that $\oplus$ing with $\tilde H$ gives a bijection between even spanning subgraphs withoutht $e_0$ and even spanning subgraphs with $e_0$. $\endgroup$ – Hw Chu Dec 20 '17 at 23:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.