欧拉图论定理
定理内容
-
若一个平面连通图
GG
G
有
VV
V
个顶点，
EE
E
条边，
FF
F
个面（包括整个图之外的面），则
V−
E
+
F
=
2
V-E+F=2
V
−
E
+
F
=
2
。
证明
- 不妨尝试用归纳法。
-
只有一个点，即
V=
1
,
E
=
0
,
F
=
1
V=1,E=0,F=1
V
=
1
,
E
=
0
,
F
=
1
，满足
V−
E
+
F
=
2
V-E+F=2
V
−
E
+
F
=
2
； -
加入一条边，连接上一个新点和一个原有的点，即
(V
+
1
)
−
(
E
+
1
)
+
F
=
V
−
E
+
F
=
2
(V+1)-(E+1)+F=V-E+F=2
(
V
+
1
)
−
(
E
+
1
)
+
F
=
V
−
E
+
F
=
2
； -
加入一条边连接原有的两个点，即
V−
(
E
+
1
)
+
(
F
+
1
)
=
V
−
E
+
F
=
2
V-(E+1)+(F+1)=V-E+F=2
V
−
(
E
+
1
)
+
(
F
+
1
)
=
V
−
E
+
F
=
2
。 - 至此，结论得证。