グラフ$G$について、
とします。
最初すべての頂点が白色であるとし、全ての頂点を赤か黒に塗分けていきます。ただし同じ色が隣り合ってはいけません。
白色である頂点$v$に着目します。
最初$v$の連結成分に含まれる全ての頂点（以降$vset$と呼びます）はまだ白色ですので、$v$を赤色で塗ってしまいます。そして隣接する頂点を黒で塗り、それらから隣接する頂点を赤で塗り…という風に$vset$を全て塗っていきます。
順番は適当で構いませんが、分かりやすさのために深さ優先探索で塗っていくことにします。
ここで気になる点として、同じ色が隣り合うことはないのか？ということです。
同じ色が隣り合ってしまうのは、一般性を失わず「$v_a$を赤で塗ったので隣接する$v_b$を黒で塗ろうとしたら、$v_b$の隣接頂点である$v_c$がすでに黒だった」というシチュエーションです。この状況を仮定します。
このとき$v_c$がすでに塗られていることから、$v_a$と$v_c$を結ぶ道として$v_b$を含まないものが存在します。すなわち$v_a, v_b, v_c$を含むような閉路が存在するということです。
$v_a$は赤で$v_c$は黒ですから、$v_a$から$v_c$への道の長さは奇数長です。よってこの道に$(v_a, v_b)$と$(v_b, v_c)$を加えた閉路も奇数長です。
一方条件Aより任意の閉路は偶数長ですので、これは矛盾です。
したがって仮定したようなシチュエーションが発生することはなく、$vset$は赤か黒で塗り分けることができます。
他の連結成分についても同様の議論が成り立ち、グラフ$G$は赤と黒に塗分けられる、つまり二部グラフであることが示せました。
$G$は二部グラフなので、Gの頂点集合は互いに素な頂点集合$V_1, V_2$に分けたうえで全ての辺が$V_1$と$V_2$の点を結んだものとできます。
閉路には$V_1$の頂点と$V_2$の頂点が交互に含まれるので、その長さは必ず偶数になります。
AならばBのよりスマートな証明を思いつきました。
グラフ$G$が木であれば二部グラフであることは自明（適当な根から赤と黒に塗り分けていけばよいです）なので、$G$が木でない場合を考えます。
$G$の適当な辺を除いて得られる木を$T$とします。すなわち、$T$に辺を加えていくことで$G$にすることができます。
$T$は自明に二部グラフであり、赤と黒に塗り分けることができます。
このとき、$G$に含まれるが$T$に含まれない辺を一本ずつ加えていくという手順を考えます（厳密には数学的帰納法を使います）。
辺を加える際に、$T$は木なので必ず閉路ができます。加えた辺$e$に接続している頂点$(v, w)$が同じ色であると仮定します。
$v$と$w$が同じ色なので、閉路のうち$e$を含まない道は偶数長である。この道に$e$を加えた閉路は奇数長になるため、Aと矛盾します。
したがってこの手順を繰り返した時、二部グラフであることを保ったまま$G$を構成することができます。