二分图(二部图)：G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边<i,j>所关联的两个顶点i和j分别属于这两个不同的顶点集，则称图G为一个二分图。
满足下面的无向图 G = < V , E > 有非空集合 X , Y : X ∪ Y = V , X ∩ Y = ? 且每条边 { v i , v j } ∈ E 都有 : v i ∈ X ∧ v j ∈ Y 或者 v i ∈ Y ∧ v j ∈ X 称为二分图 ( b i p a r t i t e g r a p h ) 可以用 G = < X , E , Y > 表示二分图 \begin{array}{l} 满足下面的无向图G=<V,E>\\ 有非空集合X,Y:X\cup Y=V,X\cap Y=\varnothing\\ 且每条边\{v_i,v_j\}\in E 都有:\\ v_i\in X\wedge v_j\in Y或者v_i\in Y\wedge v_j\in X\\ 称为二分图(bipartite\ graph)\\ 可以用G=<X,E,Y>表示二分图 \end{array} 满足下面的无向图G=<V,E>有非空集合X,Y:X∪Y=V,X∩Y=?且每条边{
vi?,vj?}∈E都有:vi?∈X∧vj?∈Y或者vi?∈Y∧vj?∈X称为二分图(bipartite graph)可以用G=<X,E,Y>表示二分图?
图G是二分图$\iff $图G至少有两个顶点，而且G中所有回路的长度都是偶数
证明：
必要性
只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同 不失一般性，设一回路从 X 部出发，则下一顶点在 Y 部， 回路上的顶点 X 、 Y 部交替，故 X 部点的数量与 Y 部点数量相同。 顶点数是偶数，边的数量也是偶数 \begin{array}{l} 只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同\\ 不失一般性，设一回路从X部出发，则下一顶点在Y部，\\回路上的顶点X、Y部交替，故X部点的数量与Y部点数量相同。\\ 顶点数是偶数，边的数量也是偶数 \end{array} 只有一个点不够二分，故至少有两个顶点。回路的边数和顶点数相同不失一般性，设一回路从X部出发，则下一顶点在Y部，回路上的顶点X、Y部交替，故X部点的数量与Y部点数量相同。顶点数是偶数，边的数量也是偶数?
充分性
任意取顶点 v , 取 V 1 = { v i ∣ v i 与 v 的距离为偶数 } , V 2 = V ? V 1 , 证明 V 1 , V 2 内部顶点间没有边 ( 反证法 ) 如果有边 { v i , v j } ∈ E v i , v j ∈ V 1 那么 v 到 v i , v j 距离都是偶数 , v → v i → v j → v 这个 回路的长度是奇数 , 和条件矛盾 , V 2 同理 所以 G 是个二分图 < V 1 , E , V 2 > \begin{array}{l} 任意取顶点v,取V_1=\{v_i|v_i与v的距离为偶数\},\\ V_2=V-V_1,证明V_1,V_2内部顶点间没有边(反证法)\\ 如果有边\{v_i,v_j\}\in E\quad v_i,v_j\in V_1\\ 那么v到v_i,v_j距离都是偶数,v\rightarrow v_i\rightarrow v_j \rightarrow v这个\\ 回路的长度是奇数,和条件矛盾,V_2同理\\ 所以G是个二分图<V_1,E,V_2> \end{array} 任意取顶点v,取V1?={
vi?∣vi?与v的距离为偶数},V2?=V?V1?,证明V1?,V2?内部顶点间没有边(反证法)如果有边{
vi?,vj?}∈Evi?,vj?∈V1?那么v到vi?,vj?距离都是偶数,v→vi?→vj?→v这个回路的长度是奇数,和条件矛盾,V2?