◀ ▲ ▶Branches / Graph-theory / Proof

Proof

(related to Theorem: Euler Characteristic for Planar Graphs)

• By hypothesis, $G$ is a connected planar graph with a planar drawing consisting of \(v\) vertices, \(e\) edges and \(f\) faces.
• We may assume that $v\ge 1,$ since a connected graph requires at least one vertex.
• First, we observe: If the formula $v-e+f=2$ holds for a multigraph (i.e. an undirected graph with some loops and/or multiple edges), then it also holds for a simple graph obtained from this multigraph by removing all loops and replacing all multiple edges by simple edges.
  • For if we remove a loop or remove in a given multiple edge one of the edges, the numbers $e$,$f$ and $v$ change as follows: * $e\to e-1$ * $f\to f-1$ * $v\to v$ * an the formula remains unchanged.
• Therefore, we can assume that we have a connected simple graph, for which we have to check the formula $v-e+f=2.$
• Case $v=1$:
  • We have $e=0$ and $f=1$ (infinite face) and the formula is correct.
• Case $v=2$:
  • We have $e=1$ and $f=1$ (infinite face) and the formula is again correct.
• Case $v > 2.$
  • Since the graph is connected, we can remove edges one by one to get the case $v=2.$ When removing the edges, we have again two sub-cases: * Case a) The to-be-removed edge has one vertex with degree $=1$ and the other with degree $ > 1$. * In this case, removing the edge would disconnect the graph unless we also remove the vertex with degree $=1$. Thus, * $e\to e-1$ (the removed edge) * $f\to f$ (the surrounding face of the removed edge does not change). * $v\to v-1$ (the removed vertex with degree $=1$) * Thus, the formula $v-e+f=2$, if correct, does not change. * Case b) Both vertices incident to the to-be-removed edge have a degree $ > 1$. * In this case, removing the edge will not disconnect the graph and we do not have to remove any vertices. Thus, * $e\to e-1$ (the removed edge), * $f\to f-1$ (two faces incident to the removed edge are melted together to one face), * $v\to v$ (no removed vertices). * Thus, the formula $v-e+f=2$, if correct, does not change.
  • Altogether, we have shown for the case $v > 2$ that we can transform the graph to the case $v=2,$ for which we have already proven the formula \[v-e+f=2.\]
• It follows that the formula holds for all connected planar graphs with a planar drawing.
  ∎

Thank you to the contributors under CC BY-SA 4.0!

Github:

References

Bibliography

1. Aldous Joan M., Wilson Robin J.: "Graphs and Applications - An Introductory Approach", Springer, 2000