定理41.1和定理412表明,一个图G可一笔画成的充分必要条件是G至多有2个奇 度顶点。一般地,有下述推论 推论411一个连通图可k笔画成当且仅当它最多有2k个奇度顶点。 证明留作习题 Noida于1973年发现,在一个欧拉图中,对任何一条边,经过它的圈的个数都是奇数 1984年, Mckee又证明这个条件是充分的。这样便形成了对欧拉图的另一种刻画 定理413一个非平凡连通图G是欧拉图的充分必要条件是G的每条边含在奇数个圈上 证明:必要性:设G是欧拉图,则G的所有顶点都是偶数度的。任取G的一条边e=l, 因G有欧拉闭迹,故G′=G-e是连通图。令M表示G’中所有使顶点u恰好出现一次的 不同的uv迹组成的集合,这里两条迹相同是指两条迹的边数相同且每一步使用的边相同 因此两条迹不同要么至少其中一条迹上有另一条迹所没有的边,要么两条迹使用边的次序不 同。我们先来证明M含有奇数条迹 从顶点ν出发有奇数条边可作为迹的始边。一旦始边被确定,则这条迹就要继续到下 个顶点w。由于除w外w关联的边有奇数条,所以迹的第二条边有奇数种选择。如此继续 直至到达迹的另一个端点u。这表明始边使用w的y迹有奇数条。对每一条始边都是如 此,因此不同的uv迹有奇数条。这里需要说明的是,如果迹中途重复经过某个顶点,上述 递推过程仍然成立 假设T是G′中一条包含u恰好一次的u-v迹,但不是一条uv路,则T必定重复经过 了某些顶点,如果重复经过了顶点η,意味着T包含一条v1-V1闭迹C,此时将C“逆向” 使用,T上其它边不变,便得到另一条u-y迹,我们称其为与T同类的u迹。可见,如果 条u迹重复经过k个点(多次经过的同一点的计重复经过次数),则经这种逆向变换可 获得2k个同类uy迹。这种分类构成一个等价关系,因此形成了对有重复点的v迹集合 的划分。划分出的每一个等价类有偶数个条uv路。这说明有重复点的u-v迹总共有偶数条。 有以上两方面知,G’=G-e中共有奇数条顶点不重复的v迹(即vv路),因此, G中共有奇数个含有边e的圈 充分性:设G的每条边含在奇数个圈上,希望证明G的每个顶点都是偶数度的。任取 顶点v,设v关联的边共有k条,分别为e1,e2,…,ek。与这些边相应,构造一个有重边的 图H如下:顶点集H={4,2…,4},对于每个l,相应于每个既含有e也含有某个e的 圈,在u,和u2之间连一条边 由于e含在奇数个圈上,且每个经过e的圈必经过e,e2,…,e4中某条其它边,因此H 中顶点L1的度为奇数由的任意性H中每个点的都是奇数由公式2E(H)=∑d(u)知, H的顶点个数k必须是偶数,从而可知在G中顶点v关联偶数条边。由v的任意性,G中 所有点都是偶数度顶点,故为欧拉图。证毕。3 定理 4.1.1 和定理 4.1.2 表明，一个图 G 可一笔画成的充分必要条件是 G 至多有 2 个奇 度顶点。一般地，有下述推论。 推论 4.1.1 一个连通图可 k 笔画成当且仅当它最多有 2k 个奇度顶点。 证明留作习题。 Toida 于 1973 年发现，在一个欧拉图中，对任何一条边，经过它的圈的个数都是奇数。 1984 年，Mckee 又证明这个条件是充分的。这样便形成了对欧拉图的另一种刻画。 定理 4.1.3 一个非平凡连通图 G 是欧拉图的充分必要条件是 G 的每条边含在奇数个圈上。 证明：必要性：设 G 是欧拉图， 则 G 的所有顶点都是偶数度的。任取 G 的一条边 e = uv, 因 G 有欧拉闭迹，故G G ′ = − e 是连通图。令 M 表示G′中所有使顶点 u 恰好出现一次的 不同的 u−v 迹组成的集合，这里两条迹相同是指两条迹的边数相同且每一步使用的边相同， 因此两条迹不同要么至少其中一条迹上有另一条迹所没有的边，要么两条迹使用边的次序不 同。我们先来证明 M 含有奇数条迹。 从顶点 v 出发有奇数条边可作为迹的始边。一旦始边被确定，则这条迹就要继续到下一 个顶点 w。由于除 vw 外 w 关联的边有奇数条，所以迹的第二条边有奇数种选择。如此继续， 直至到达迹的另一个端点 u。这表明始边使用 vw 的 u−v 迹有奇数条。对每一条始边都是如 此，因此不同的 u−v 迹有奇数条。这里需要说明的是，如果迹中途重复经过某个顶点，上述 递推过程仍然成立。 假设 T 是G′中一条包含 u 恰好一次的 u−v 迹，但不是一条 u−v 路，则 T 必定重复经过 了某些顶点，如果重复经过了顶点 v1，意味着 T 包含一条 v1 −v1 闭迹 C，此时将 C“逆向” 使用，T 上其它边不变，便得到另一条 u−v 迹，我们称其为与 T 同类的 u−v 迹。可见，如果 一条 u−v 迹重复经过 k 个点（多次经过的同一点的计重复经过次数），则经这种逆向变换可 获得2k 个同类 u−v 迹。这种分类构成一个等价关系，因此形成了对有重复点的 u−v 迹集合 的划分。划分出的每一个等价类有偶数个条 u−v 路。这说明有重复点的 u−v 迹总共有偶数条。 有以上两方面知，G G ′ = − e 中共有奇数条顶点不重复的 u−v 迹（即 u−v 路），因此， G 中共有奇数个含有边 e 的圈。 充分性：设 G 的每条边含在奇数个圈上，希望证明 G 的每个顶点都是偶数度的。任取 顶点 v， 设 v 关联的边共有 k 条，分别为 1 2 ,, , k ee e " 。与这些边相应，构造一个有重边的 图 H 如下：顶点集 H {, , , } 1 2 k = uu u " ，对于每个 i u ，相应于每个既含有 i e 也含有某个 j e 的 圈，在 i u 和 j u 之间连一条边。 由于 i e 含在奇数个圈上，且每个经过 i e 的圈必经过 1 2 ,, , k ee e " 中某条其它边，因此 H 中顶点 i u 的度为奇数。由 i u 的任意性，H 中每个点的都是奇数。由公式 1 2 (H) ( ) k i i ε d u = = ∑ 知， H 的顶点个数 k 必须是偶数，从而可知在 G 中顶点 v 关联偶数条边。由 v 的任意性，G 中 所有点都是偶数度顶点，故为欧拉图。证毕