Proving the generalization of Euler's formula for a graph $G$ with $k$ connected components: $V(G)-E(G)+F(G) = k+1$

1k Views Asked by At

Let $G$ be a planar graph.

Let $V(G)$ denote its numbers of vertices, $E(G)$ its number of edges and $F(G)$ its number of faces.

Show that if $G$ has $k$ connected components, then $$V(G)-E(G)+F(G) = k+1$$ which generalizes Euler's formula for a connected planar graph: $V(G)-E(G)+F(G) = 2$


Proof by induction in k

Initial step ($k=1$):

This follows directly from Eulers formula.

Induction step:

Suppose the above claim is true for $k$ connected components. We want to show this implies it's true for $k+1$ connected components as well.

Let $\tilde{G}$ be a planar graph with $k+1$ connected components. Consider the following division of $\tilde{G}$ into a graph $\tilde{G_k}$ that has $k$ connected components and $\tilde{G_1}$ that is itself connected.

By the induction assumption $V(\tilde{G_k})-E(\tilde{G_k})+F(\tilde{G_k}) = k+1$ and by the initial step $V(\tilde{G_1})-E(\tilde{G_1})+F(\tilde{G_1}) = 2$.

Note that $\tilde{G_k}$ and $\tilde{G_1 }$ share excactly 1 face so we have

$$V(\tilde{G})-E(\tilde{G})+F(\tilde{G})= (V(\tilde{G_k})+V(\tilde{G_1}))-(E(\tilde{G_k})+E(\tilde{G_1}))+(F(\tilde{G_k})+F(\tilde{G_1})-1)$$

$$=V(\tilde{G_k})-E(\tilde{G_k})+F(\tilde{G_k})+V(\tilde{G_1})-E(\tilde{G_1})+F(\tilde{G_1})-1=k+1+2-1=k+2$$

which proves the desired result.

$\blacksquare$

My question is: Is my proof good/valid? Should I be more precise why they share a face? And if so, how can I do that?