证明：
必要性
：设
0
1
0
v
v
v
v
C
k
=
是二部图
)
,
(
E
Y
X
G
∪
=
的一个圈。无妨设
X
v
∈
0
，
由二部图的定义知，
Y
v
∈
1
，
X
v
∈
2
，
，一般地，
X
v
i
∈
2
，
Y
v
i
∈
+
1
2
，
（
,
1
,
0
=
i
）
。
又因
X
v
∈
0
，故
Y
v
k
∈
，因而
k
是奇数。注意到圈
C
上共有
1
+
k
条边，因此是偶圈。
充分性
：设
G
不含奇圈。取
)
(
G
V
u
∈
，令
}
)
,
(
|
)
(
{
odd
v
u
d
G
V
v
X
＝
∈
=
，
}
)
,
(
|
)
(
{
even
v
u
d
G
V
v
Y
＝
∈
=
。
任取一条边
2
1
v
v
e
=
，欲证
2
1
,
v
v
分属于
X
和
Y
。设
P
，
Q
分别是
u
到
2
1
,
v
v
的最短路。
（
1
）如果
1
2
v
v
Q
P
+
=
或
2
1
v
v
P
Q
+
=
，则
2
1
,
v
v
到
u
的距离奇偶性相反，
2
1
,
v
v
分属于
X
和
Y
。
（
2
）否则，设
u
′
是
P
与
Q
的最后一个公共顶点，因
P
的
)
,
(
u
u
′
段和
Q
的
)
,
(
u
u
′
段都是
u
到
u
′
的最短路，故这两段长度相等。
假如
P
，
Q
的奇偶性相同，
则
P
的
)
,
(
1
v
u
′
段和
Q
的
)
,
(
2
v
u
′
段奇偶性相同，
这两段与边
e
构成一个奇圈，与定理条件矛盾。可见
P
，
Q
的奇偶性不同，从而
2
1
,
v
v
分属于
X
和
Y
。
这便证明了
G
是一个二部图。
证毕。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024