欧拉公式（平面图）
概述
欧拉公式（Euler’s Formula for Planar Graphs）：对于任意连通的平面图 ，其顶点数 、边数 和面数 （含外部无限面）满足 。
定理陈述
形式化陈述
定理（欧拉公式）： 设 是一个连通的平面图（planar graph）， 为顶点数， 为边数， 为平面嵌入中的面数（faces，包括外部无限面），则
推广形式：若 是有 个连通分支的平面图，则
注意：该公式要求图是连通的且已给定平面嵌入。面数 依赖于具体的平面嵌入方式，但 的值恒为 。
证明概要
证明思路（对边数归纳）
详细证明
对边数 使用数学归纳法。
基础步：
- 若 ：图只有一个孤立顶点，，，（仅有外部面），则 。
- 若 ：连通图只有两个顶点和一条边，，，（外部面），则 。
归纳步：
假设对所有边数小于 的连通平面图，欧拉公式成立。考虑边数为 的连通平面图 。
情况一： 中存在非桥边（non-bridge edge）
设 是 中的一条非桥边（删除后图仍连通）。删除 得到图 ：
- 仍是连通的（因为 不是桥）。
- 的边数为 。
- 删除 后， 两侧的两个面合并为一个面，所以 的面数为 。
- 顶点数不变，仍为 。
由归纳假设：
化简得 。
情况二： 中每条边都是桥
此时 是一棵树（tree）。树的面数恒为 （只有外部面），且树的边数 。
因此：
综合两种情况，由数学归纳法，欧拉公式对所有连通平面图成立。
关键推论
-
推论1（平面图的边数上界）：若 是有 个顶点的简单连通平面图，则 。若 还不含三角形，则 。
证明：每个面至少由 条边围成（简单图无环和重边），故 。代入欧拉公式得 ，即 ，化简得 。
-
推论2（ 非平面图）： 有 ，。若 是平面图，则 ，但 ，矛盾。
-
推论3（ 非平面图）： 有 ，，且不含三角形（二部图）。若 是平面图，则 ，但 ，矛盾。
-
推论4（正则平面图的限制）： 和 的非平面性是 Kuratowski 定理 的基础。
应用场景
- 判断平面性：通过边数上界 快速判断某些图是否为非平面图。
- 图的着色：欧拉公式是证明五色定理和四色定理的重要工具。
- 多面体理论：凸多面体的顶点数 、棱数 、面数 满足 。正多面体（柏拉图立体）的分类可直接由欧拉公式推出。
- 拓扑学：欧拉示性数 是曲面拓扑学的基础概念，可推广到任意可定向闭曲面。
数值示例
立方体图：（顶点），（棱），（面，含外部面则为 ）。
验证：。
四面体图（）：，，。
验证：。