----- > [!proposition] Proposition. ([[Euler's graph formula]]) > For a [[simple graph|simple]] [[planar graph]] $G=(V,E)$ that is [[connected graph|connected]], we have $|V|-|E|+|F|=2$, where $|F|$ denotes the number of [[graph face|faces]] on $(V,E)$. > [!proof]- Proof. ([[Euler's graph formula]]) Consider the [[dual graph]] $D$ of $G$. Form a [[spanning tree]] $T$ of $G$ and note that it induces a complementary spanning tree $S$ of $D$,![[CleanShot 2023-09-13 at 09.34.03.jpg]] since it would require a [[cycle]] in $T$ to prevent $S$ from spanning $G$, and $S$ cannot have cycles because this would prevent $T$ from being a [[tree]] (for symmetric reasoning). \ By [[tree iff has n-1 edges|tree iff has n-1 edges]], we have that $T$ has $|V|-1$ edges, while (recalling that the nodes of $S$ are [[graph face|faces]]) $S$ has $|F |-1$ edges. $T$ and $S$ are complementary, hence we must have $\begin{align} |E|=|V|-1+|F|-1, \end{align}$ which simplifies to $|V|-|E|+|F|=2$. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```