西安电子科技大学$6.2.4二部图的充要条件软件学院定理！设G是无向图，G是二部图当且仅当G中所有回路的长度均为偶数。证明：(必要性）设G是具有互补结点子集X和Y的二部图。C=(vO，V1，v2，，vk，vO)是G中的任一回路。不妨设vOEX，则有结点v2,v4..EX，v1,v3...EY,并且k必为奇数，否则vO，vkEX且(vk，vO)EE这与G是二部图矛盾。这样C中共有k+1条边，故回路C的长度为偶数。西安电子科技大学 §6.2.4 二部图的充要条件 软件学院 证明：（必要性） 设G是具有互补结点子集X和Y的二部图。C=(v0, v1, v2, ., vk, v0)是G中的任一回路。 不妨设v0∈X，则有结点v2, v4.∈X，v1, v3.∈Y， 并且k必为奇数，否则v0, vk∈X且(vk, v0)∈E这与G是二部 图矛盾。这样C中共有k+1条边，故回路C的长度为偶数