\chapter{Euler公式}
\section{平面图}
\begin{definition}
    如果图$G = (V, E)$的所有顶点和边可以在一个平面上图示出来，而使各边仅在顶点处相交，则图$G$称为平面图，它的平面图示称为图$G$的\newnoun{平图}{planar graph}；否则称$G$为非平面图。
\end{definition}

需要注意的是，有些图形从表面上看有几条边是相交的，但是不能就此肯定它不是平面图，下面这个图就是一个例子：
\begin{figure}[H]
    \centering
    \subfloat[最初的图形]{
        \begin{tikzpicture}
            \node[draw=black, circle] (a) at (0,0) {};
            \node[draw=black, circle] (b) at (3,0) {};
            \node[draw=black, circle] (c) at (3,2) {};
            \node[draw=black, circle] (d) at (0,2) {};
            \node[draw=black, circle] (e) at (1.5,3) {};
            \draw (b)--(a)--(d)--(c)--(b)--(e)--(a)--(c)--(e)--(d);
            \draw[opacity=0] (a).. controls (4,-1) ..(c);
        \end{tikzpicture}
    }
    \hspace{2cm}
    \subfloat[调整边的画法后的图形]{
        \begin{tikzpicture}
            \node[draw=black, circle] (a) at (0,0) {};
            \node[draw=black, circle] (b) at (3,0) {};
            \node[draw=black, circle] (c) at (3,2) {};
            \node[draw=black, circle] (d) at (0,2) {};
            \node[draw=black, circle] (e) at (1.5,3) {};
            \draw (b)--(a)--(d).. controls (2,4.5) ..(c)--(b)--(e)--(a).. controls (4,-1) ..(c)--(e)--(d);
        \end{tikzpicture}
    }
\end{figure}

\section{面和边界}
\begin{definition}
    设$G$是一连通平面，由图中的边所包围的区域，在区域内既不包含图的顶点，也不包含图的边，这样的区域称为$G$的一个\newnoun{面}{face}，有界的区域称为有界面，无界的区域称为无界面。

    包围一个面的的诸边所构成的回路称为这个面的边界。面$F$的边界的长度称为该面的度数，记为$d(F)$。
\end{definition}

\begin{figure}[H]
    \centering
    \begin{tikzpicture}
        \node[draw=black, circle] (a) at (-3,0) {};
        \node[draw=black, circle] (b) at (0,0) {};
        \node[draw=black, circle] (c) at (1,2) {};
        \node[draw=black, circle] (d) at (1,-2) {};
        \node[draw=black, circle] (e) at (5,0) {};
        \node[draw=black, circle] (f) at (2,0) {};
        \draw (f)--(e)--(c)--(d)--(b)--(c);
        \draw (b)--(a).. controls (1,4).. (e) .. controls (4,-1) and (3,-1.5).. (d) .. controls (0,-1.8) and (-2, -1).. (a);
        \node at (-3.5,0) {$A$};
        \node at (-0.3, 0.3) {$B$};
        \node at (1.3,2.3) {$C$};
        \node at (1, -2.5) {$D$};
        \node at (5.5,0) {$E$};
        \node at (2, 0.5) {$F$};
        \node at (-0.7,-0.7) {$r_1$};
        \node at (0.5,0) {$r_2$};
        \node at (1.5, 1) {$r_3$};
        \node at (0,1) {$r_4$};
        \node at (4,2) {$r_5$};
    \end{tikzpicture}
\end{figure}

在上图中，$d(r_1) = 3, d(r_2) = 2, d(r_3) = 5, d(r_4) = 4, d(r_5) = 3$。

\begin{theorem}
    有限平图面的度数之和为其边数的两倍：
    \[\sum d(f) = 2 \vert E \vert\eqper\]
\end{theorem}

\begin{proof}
    任意一条边只可能是下面两种情况中的一种：
    \begin{enumerate}
        \item 它是两个面的共同边，在两个面的度中分别被计算了一遍；
        \item 它是一个面边界的重复，在这个面的度中被计算了两遍。\qedhere
    \end{enumerate}
\end{proof}

\section{欧拉公式}
\begin{theorem}[Euler's Formula]
    设$G$为一连通平图，$v$为其顶点数，$e$为其边数，$f$为其面数，那么有
    \[v - e + f = 2\eqper\]
\end{theorem}

\begin{proof}
    对面的数量进行归纳。

    若$f = 1$，则$G$为一棵树，且$e = v - 1, f = 1$，因此$v - e + f = v - v + 1 + 1 = 2$成立。

    设对于面数小于$n$的所有连通平图定理成立。那么对于面数为$n$的连通平图$G$，任选$G$的一条非桥的边$a$，那么$G-a$是连通平图，且$f(G-a) = n - 1$。由归纳假设有$v(G-a) - e(G-a) + f(G-a) = 2$，同时$v(G-a) = v(G), e(G-a) = e(G) - 1, f(G-a) = f(G) - 1$，因此$v(G) - e(G) + f(G) = 2$。
\end{proof}

\begin{theorem}
    设$G$为一简单连通平图，其点数$v \geq 3$，其边数为$e$，那么$e \leq 3v - 6$。
\end{theorem}

\begin{proof}
    设$G$的边数为$f$，那么每一个面的度数都不小于3；同时各面的度数和为$2e$，这意味着
    \[3f \leq \sum d(F) = 2e, f \leq \frac{2}{3}e\]
    代入Euler's Formula，
    \[2 = v - e + f \leq v - e + \frac{2}{3}e\]
    整理可得$e \leq 3v - 6$。
\end{proof}

这个定理不是充分的，满足此条件的图有可能不是平图。

上面的定理利用了``每个面的度都不小于3''这一事实。如果有图的面度都不小于$k$呢？
\begin{corollary}
    对每个面的度至少为$k$的连通平图，有
    \[e \leq \frac{k(v-2)}{k-2}\eqper\]
\end{corollary}

证明与前面的定理是类似的。