由来

定义

定理及证明

推论

由来

图论的第一篇论文是著名数学家欧拉于1736年发表的，这篇论文对当时举世瞩目的数学难题——哥尼茨堡七桥问题作出了否定的答案。

哥尼斯堡（Konigsberg）是现在俄罗斯的加里宁格勒，该城位于普瑞格尔（Pregel）河畔，城区由两岸及河中的两个小岛四个区A，B，C，D组成，全城由七座桥相连，如图所示。

当时城中居民热衷于这样一个问题：游人从城中某一地点出发，能否行遍七座桥各1次而回到原地？问题看来并不复杂，但谁也解决不了。于是有人就去请教欧拉。欧拉把四块陆地抽象成4个点，每座桥抽象成连接两点的线段，而得到右下图。从而问题就变成：从某一顶点出发，能否不重复地行遍所有的边而回到这个顶点？

如果答案是肯定的，那么图中各边连接的每个顶点，既有“进入”这个点的边，又有“走出”这个点的边。就是说每个顶点必须是偶次点。但右图四个顶点都是奇次点，所以答案是否定的。

定义

迹和闭迹 图G的顶点与边的交错序列：v0e1v1e2v2…vl-1elvl (l>0)

其中ei+1（i=0,1,…,l-1）的端点是vi与vi+1,且i≠j时，ei不等于ej(1≤i,j≤l),叫做图G的迹，如果v0与vl

重合，则称为闭迹。

欧拉（闭）迹 通过图G的所有边的（闭）迹，称为欧拉（闭）迹。

定理及证明

定理 设G是一个连通图，则（1）G是欧拉迹的充要条件是G中有且仅有两个奇次顶点；（2）G是欧拉闭迹的充要条件是G中全是偶次顶点。

证明 仅证（2）。必要性是显然的，下证充分性，对q(G)应用归纳法。

每个顶点皆为偶次的连通图，边数最少者为K3。这时命题成立。假设3≤q(G)≤k的图G命题成立。考虑 q(G)=k+1的图G，因为没有1度顶点，故G不是树，G上有圈，假设C是G的一个圈，把C的所有边从G上删除，所得的图G'的顶点仍然都是偶次的。设G'是由无公共顶点的连通图G1，G2，…，Gl组成。不妨设前m个是平凡图（即每个顶点的度都是0的图）。由归纳假设，G1，G2，…，Gm有欧拉闭迹W1，W2，…，Wm，于是W1∪W2∪…∪Wm∪C即为G的欧拉闭迹。

推论

易知，一个能够一笔画的图，就是有欧拉迹或欧拉闭迹的图；反之，一个有欧拉迹或欧拉闭迹的图，必是能一笔画的图。根据上面的定理，我们有

推论 设G是一个连通图。则图G能一笔画的充要条件是G中没有奇次顶点或有且只有两个奇次顶点。