Theorems Related to Graph Theory
\(\mathbf{Theorem\ 1}.\)若有从\(u\)到\(v\)的通路，则存在从\(u\)到\(v\)的基本通路。
\(\mathbf{Inference:}\)若有通过\(u\)的回路，则存在通过\(u\)的基本回路。
\(\mathbf{Theorem\ 2}.\)在\(n\)阶图中，基本通路长度不大于\(n-1\)，基本回路长度不大于\(n\)。
\(\mathbf{Inference:}\)在\(n\)阶图中，若两个不同节点间存在通路，则两个节点之间至少存在一条长度不大于\(n-1\)的基本通路；若存在经过一个节点的回路，则至少存在经过此节点一条长度不大于\(n\)的基本回路。
\(\mathbf{Theorem\ 3}.\)一个有向图是强连通图当且仅当图中存在一条经过所有节点的回路。
\(\mathbf{Theorem\ 4}.\)一个有向图是单向连通图当且仅当图中存在一条经过所有节点的通路。
\(\mathbf{Theorem\ 5}.\)\(\mathbf{握手定理}：\)每个图所有节点度数之和是边数的两倍。
\(\mathbf{Inference\ 1:}\)每个图的奇度数节点的个数为偶数。
\(\mathbf{Inference\ 2:}\)在有向图中，所有节点的入度和等于出度和，等于边数。
树：图\(G<V,E>\)连通且无回路
满足以下性质：
- \(|V|=|E|+1\)
- \(G\)中任何边均为割边
- \(G\)中每对节点有唯一的基本通路
- 在\(G\)中任意两个结点间增加一条新边，则得到唯一的一条含新边的基本回路
\(\mathbf{Theorem\ 6}.\)任意的非平凡树至少有两片树叶。
\(\mathbf{Proof:}\)
树\(T\)的边数为\(m\)，节点数为\(n\)，树叶数为\(t\)，则由握手定理：
\(\mathbf{Theorem\ 7}.\)图\(G\)存在生成树当且仅当图\(G\)是连通的。
\(\mathbf{Theorem\ 8}.\)在\(m\)元完全树中，树叶数为\(t\)，分支点数为\(i\)，则满足：
- 欧拉路径： 图中一条经过每条边恰好一次的通路。(起点终点可不相同)
- 欧拉回路：图中一条经过每条边恰好一次的回路。(起点终点相同)
- 欧拉图：包含欧拉回路的图。
- 半欧拉图：不包含欧拉回路，但是包含欧拉路径的图。
\(\mathbf{Theorem\ 9}.\)无向图是欧拉图当且仅当图中所有节点都是偶度数节点。
\(\mathbf{Proof:}\)
这里证明必要性：
若无向图\(G\)是欧拉图，即图\(G\)包含欧拉回路，则必经过途中每个节点\(k\)次，则此节点度数为\(2k\)，得证。
\(\mathbf{Theorem\ 10}.\)无向图是半欧拉图当且仅当图中有\(0\)个或\(2\)个奇度数节点
\(\mathbf{Proof:}\)
这里证明必要性：
若无向图\(G\)是半欧拉图，即图\(G\)包含欧拉通路，则除去起点和终点，必经过每个节点\(k\)次，则这些节点度数为\(2k\)，\(2\)个奇度数节点仅为起点和终点，当起点和终点相同时，奇度数节点为\(0\).
- 哈密顿路径：图中一条访问每个顶点恰好一次的路径。
- 哈密顿回路：图中一条访问每个顶点恰好一次的回路。(起点和终点相同)
- 哈密顿图：包含哈密顿回路的图。
- 半哈密顿图：不包含哈密顿回路，但包含哈密顿路径的图。
\(\mathbf{Theorem\ 11}.\)若图 \( G = \langle V, E \rangle \) 是哈密顿图，那么对于顶点集 \( V \) 的任意非空真子集 \( S \)，把 \( S \) 这些顶点从图里去掉后，剩下的图的连通分支数 \( P(G - S) \) 满足：
\(\mathbf{Inference:}\)若图 \( G = \langle V, E \rangle \) 是半哈密顿图，那么对于顶点集 \( V \) 的任意非空真子集 \( S \)，把 \( S \) 这些顶点从图里去掉后，剩下图的联通分支数满足：
\(\mathbf{Theorem\ 12}.\)若图\(G\)中任意两个节点\(u, v\)满足：
则图\(G\)为哈密顿图。
\(\mathbf{Theorem\ 13}.\)图\(G\)为偶图当且仅当\(G\)中任意回路的边数都为偶数。
\(\mathbf{Theorem\ 14}.\)完全图\(K_5\)及以上都是非平面图。
\(\mathbf{Theorem\ 15}.\)完全偶图\(K_{3,3}\)及以上都是非平面图。
\(\mathbf{Theorem\ 16}.\)\(\mathbf{握手定理}：\)在一个平面图中，所有面的次数之和等于图中边数的两倍。
\(\mathbf{Theorem\ 16}.\)\(\mathbf{欧拉定理}：\)设\(G<V,E>\)是平面连通图，它有\(n\)个节点，\(m\)条边，\(r\)个面，则满足：
\(\mathbf{Proof:}\)
Suppose 一个\(G\)的生成子图为生成树，则满足：
由树的性质\(4\)：在\(G\)中任意两个结点间增加一条新边，则得到唯一的一条含新边的基本回路。
每增加一条边，则\(m++，r++\)，不论增加多少条边，总有：
即：
\(\mathbf{Inference:}\)
\(G\)中任何一个面都至少由\(3\)条边围成，因此有
即：