無向圖G為二分圖的充分必要條件是，G至少有兩個頂點，且其所有回路的長度均為偶數。
證先證必要性。
設G為二分圖<X，E，Y>。由於X，Y非空，故G至少有兩個頂點。若C為G中任壹回路，令
C = (v0,v 1,v2，…，v l-1,v l = v0)
其中諸vi (i = 0,1，…，l）必定相間出現於X及Y中，不妨設
{v0,v2,v4，…，v l = v0} Í X
{v1,v3,v5，…，v l-1} Í Y
因此l必為偶數，從而C中有偶數條邊。
再證充分性。
設G的所有回路具有偶數長度，並設G為連通圖（不失壹般性，若G不連通，則可對G的各連通分支作下述討論）。
令G的頂點集為V，邊集為E，現構作X，Y，使<X，E，Y> = G。取v0ÎV，置
X = {v | v= v0或v到v0有偶數長度的通路}
Y = V-X
X顯然非空。現需證Y非空，且沒有任何邊的兩個端點都在X中或都在Y中。
由於|V|≥2並且G為壹連通圖，因此v0必定有相鄰頂點，設為v1，那麽v1ÎY；故Y不空。
設有邊（u,v），使uÎX，vÎX。那麽，v0到u有偶數長度的通路，或u = v0；v0到v有偶數長度的通路，或v = v0。無論何種情況，均有壹條從v0到v0的奇數長度的閉路徑，因而有從v0到v0的奇數長度的回路（因從閉路徑上可能刪去的回路長度總為偶數），與題設矛盾。故不可能有邊（u,v）使u,v均在X中。
“沒有任何邊的兩個端點全在Y中”的證明可仿上進行，請讀者思考。