欧拉定理的描述是：
一个连通图是欧拉图当且仅当每个点的度数是偶数。
要搞懂这个定理，首先要搞懂什么是连通图。所谓连通图是任意两点都能连接（不需要直接连接）的图。那什么又是欧拉图呢？
欧拉图Euler graph，如果图包含一个欧拉环游Euler Tour，那么就是欧拉图。那新概念又来了，什么是欧拉环游？
欧拉环游，是闭合的欧拉迹Euler trail。
欧拉迹，是经过图中所有的边恰好一次的迹。头疼啊！迹又是什么鬼？是不是要崩溃了？我用我未来另一半20年的寿命保证除了迹再也没有新概念了。
迹trail**，是一条边不重复的路径Walk*，路径不是概念哈，就是路径而已。
好了，未来另一半二十年的寿命保住了。下面先用图表示下欧拉迹,用数字和箭头表示了行走路径：
很明显，上图不是闭合的欧拉迹。根据欧拉定理，我们知道有些点的度数为3，是个奇数，所以不是欧拉图，也就不存在欧拉环游，所以不可能走完所有的路径然后再回到原点。
再给个欧拉环游的例子，加一个点，把两个奇度点连起来，变成偶度点，就成欧拉图，如下图所示：
好了，概念都清楚了，现在到了证明阶段。我将分两部分来证明。首先证明必要条件，也就是欧拉图的所有点都是偶数度点。
必要条件证明
设G为欧拉图，u为欧拉环游起点也是终点,
u
→
u
u \rightarrow u
u→u为欧拉路径，v为欧拉路径经过的任意不为u的点。假设v出现k次（环游是路径只能一次，但是点可以出现多次）。因为欧拉环游经过v时，进入是一个度，离开是一个度。所以v的度数为2k。那么对于u，如果u在路径出出现了
k
u
k_u
ku次，再加上开始结束的两次，那么u出现的次数就是
2
k
u
+
2
2k_u+2
2ku+2次。那么u也是一个偶数度点。所以所有点都是偶数度点，证明完毕。
充分条件证明
假设G为连通图，并且所有点的度数为偶数。设W为最长的迹（路径），经过了
e
1
…
e
n
e_1\dots e_n
e1…en，从
v
0
v_0
v0出发到
v
n
v_n
vn。首先，我们要证明这个迹是闭合的，然后再证明这个迹包含了所有边。
先证明最大迹
W
W
W是闭合的，利用反证法，如果终点
V
n
V_n
Vn不等于起点
V
0
V_0
V0，假设
V
n
V_n
Vn在迹中出现k次，那么
V
n
V_n
Vn的度数是2k+1，这是个奇数，不符合假设，所以
V
n
V_n
Vn就是
V
0
V_0
V0，证明完毕。
再证明最大迹
W
W
W包含了所有边。因为前面证明了最大迹W是闭合的，所以这个最大迹W是一个环。又因为图是连通图，所以再次利用反证法，如果最大迹W不包含所有边，那么必存在一条边f，f连接了最大迹W上的某一点v。那么就存在一条新的非闭合迹
W
2
W_2
W2，从v出发，沿着W回到v，再连接边f。新的迹
W
2
W_2
W2长度比是迹
W
W
W的长度大1，不符合
W
W
W是最大迹的设定。最大迹
W
W
W包含了所有边证明完毕。
最大迹
W
W
W是闭合的，并且包含了所有边，所以是欧拉图。充分条件证明完毕。
充分条件和必要条件都证明了，所以欧拉图论定理证明完毕。
欧拉定理有什么用？我们时常在公众号、短视频里见到一笔画完不能重复的智力题，欧拉定理可以帮我们快速判断能不能不重复地一步画完。例如不会被下面的短视频坑了：
