not depend on the edge numbering; so the summation in the left-hand side of both theorems is performed over the set $2^{E(G)}$ of subsets of $E(G)$. The equivalence of the theorems is now a particular case of the Moebius inversion formula [@Rota]. Namely, for any finite set $X$ the Moebius function of the set $2^X$ partially ordered by inclusion is $\mu(S,T) =
(-1)^{\#(S \setminus T)}$, where $S, T \subseteq X$. Therefore one has $$\begin{aligned}
\SumSub(&\sigma;G) = (-1)^k \alpha(G) \\
&\Longleftrightarrow \SumSub(\mu(G,H) (-1)^{\#\text{edges of H}}
\alpha(H);G) = \sigma(G) \\
&\Longleftrightarrow \SumSub((-1)^{k-\#\text{edges of H}}
(-1)^{\#\text{edges of H}}\alpha(H);G) = \sigma(G) \\
&\Longleftrightarrow \SumSub(\alpha(H);G) = (-1)^k \sigma(G).
 \end{aligned}$$

Proof of Theorem \[Th:Direct\] {#SSec:PrDirect}
------------------------------

To prove the theorem we use simultaneous induction by the number of vertices and the number of edges of the graph $G$. If $\mathcal R$ is some set of subgraphs of $G$ (different in different cases) and $\chi_{\mathcal
R}$ is the characteristic function of this set then for convenience we will write $\SumSub(f,\mathcal R) {\stackrel{\mbox{\scriptsize def}}{=}}\SumSub(f \chi_{\mathcal R},G) = \sum_{H
\in \mathcal R} f(H)$ for any function $f$ on the set of subgraphs.

Consider now the following cases:

### $G$ is disconnected.

Let $G = G_1 {\sqcup \dots \sqcup} G_m$ 