連結成分(グラフ)

2 ⇒ 1：$G$ の辺はどれも 1 つの連結成分に属し、両端点が同じ同値類にある。$S$ は同値類の和集合なので、各辺の両端点はともに $S$ に属するか、ともに $S$ に属さない。
1 ⇒ 2：$u\in S$ と $u\sim_G v$ を満たす $v$ をとり、$u$–$v$ 道 $(u=v_0,v_1,\dots,v_\ell=v)$ をとる。$v_{i-1}\in S$ なら、辺 $v_{i-1}v_i$ は $E(S,V\setminus S)$ に属さないので $v_i\in S$ である。$i$ についての帰納法で $v\in S$ となる。よって $u$ の同値類は $S$ に含まれ、$S$ はその要素の同値類の和集合である。$\square$

1 ⇒ 2：$f$ を同型とする。$(v_0,\dots,v_\ell)$ が $G$ の道なら、$f$ は隣接関係を保つ単射なので $(f(v_0),\dots,f(v_\ell))$ は $H$ の道である。逆写像 $f^{-1}$ も同型なので（グラフ の記事の命題「同型の基本性質」）、$u\sim_G v$ と $f(u)\sim_H f(v)$ は同値である。よって $f$ は各同値類 $C$ を同値類 $f(C)$ の上へ写し、$\varphi(C):=f(C)$ は同値類の間の全単射である。$u,v\in C$ について $uv\in E\iff f(u)f(v)\in E'$ なので、$f$ の $C$ への制限は $G[C]$ から $H[f(C)]$ への同型である。これで 2 と最後の主張が示された。
2 ⇒ 1：各同値類 $C$ について同型 $f_C\colon G[C]\to H[\varphi(C)]$ を選び、$v\in V$ に対し $f(v):=f_{C}(v)$（$C$ は $v$ を含む同値類）と定める。同値類は $V$ と $V'$ をそれぞれ重なりなく覆い、$\varphi$ と各 $f_C$ は全単射なので、$f\colon V\to V'$ は全単射である。
$uv\in E$ とすると、$u,v$ は同じ同値類 $C$ に属するので、$f(u)f(v)=f_C(u)f_C(v)$ は $H[\varphi(C)]$ の辺であり、$E'$ に属する。逆に $f(u)f(v)\in E'$ とする。$H$ の辺の両端点は同じ同値類に属するので、$f(u),f(v)$ はある $\varphi(C)$ に属する。$f(u)\in\varphi(C_u)$（$C_u$ は $u$ の同値類）と $\varphi$ の単射性から $C_u=C$、同様に $v\in C$ であり、$f_C$ が同型なので $uv\in E$ である。よって $f$ は同型である。$\square$

$G_v$ 以外の連結成分 $G[C]$ は $G-v$ の連結成分でもある。実際、$C$ の 2 頂点を結ぶ $G[C]$ の道は $v$ を通らないので $G-v$ の道であり、prop-ccg-closed-set により $C$ から外へ出る $G$ の辺はないので $G-v$ の辺もない。$G-v$ の頂点の同値類で $C$ を含むものは、再び prop-ccg-closed-set の 1 ⇒ 2 の議論により $C$ に含まれ、$C$ と一致する。
残りの $G-v$ の連結成分は、頂点集合 $C_v\setminus\{v\}$（$C_v$ は $G_v$ の頂点集合）を分割する。その個数を $k$ とすると $c(G-v)=c(G)-1+k$ である。$d=0$ なら $C_v=\{v\}$ なので $k=0$ で、1 が従う。
$d\ge1$ とする。$C_v\setminus\{v\}$ は $v$ の隣接頂点を含むので空でなく、$k\ge1$ である。$G-v$ の連結成分 $K\subset C_v\setminus\{v\}$ の頂点 $x$ をとり、$G$ の $x$–$v$ 道 $(x=w_0,\dots,w_r=v)$ をとると、$w_{r-1}$ は $v$ の隣接頂点であり、区間 $(w_0,\dots,w_{r-1})$ は $v$ を通らないので $G-v$ の道である。よって $K$ は $v$ の隣接頂点 $w_{r-1}$ を含む。異なる $K$ は交わらないので、$k$ は $v$ の隣接頂点の個数 $d$ 以下である。これで 2 が示された。
3：$K$ を上の連結成分とし、$v$ と $K$ の頂点を結ぶ辺の本数を $d_K$ とする。$K$ の頂点 $x$ に接続する $G$ の辺の他端は $K$ か $v$ にある。他端 $y$ が $K\cup\{v\}$ の外にあると、$y$ は $G-v$ の頂点で $x$ と隣接するので $K$ に属することになり矛盾するからである。したがって、$K$ の頂点の次数の和は、両端が $K$ にある辺を 2 回、$v$ との辺を 1 回ずつ数えて
$$ \sum_{x\in K}\deg_G(x)=2\,\lvert E\cap[K]^2\rvert+d_K $$
となる。左辺は偶数の和なので偶数であり、$d_K$ は偶数である。$K$ は $v$ の隣接頂点を含むので $d_K\ge1$、よって $d_K\ge2$ である。$v$ の各辺はちょうど 1 つの $K$ に入るので $\sum_Kd_K=d$ であり、$2k\le d$ となる。$\square$

行列 $X$ について、$\operatorname{rank}X=n-\dim\{x\in F^V\mid x^{\top}X=0\}$ である（行の個数 $n$ から左核の次元を引いたもの）。左核を調べる。
1：辺 $e$ が $u$ から $w$ へ向くとき $(x^{\top}N)_e=x_u-x_w$ なので、$x^{\top}N=0$ は「すべての辺 $uw$ で $x_u=x_w$」と同値である。この条件を満たす $x$ は道に沿って値が変わらないので、各同値類の上で定数である。逆に各同値類の上で定数なら、辺の両端点は同じ同値類にあるので条件を満たす。よって左核は「同値類ごとに定数のベクトル」全体で、次元は同値類の個数 $c(G)$ である。
2：$(x^{\top}M)_e=x_u+x_w$ であり、標数 $2$ では $x_u+x_w=x_u-x_w$ なので、1 と同じ左核になる。
3：左核の条件は「すべての辺 $uw$ で $x_w=-x_u$」である。この条件は辺ごとに両端点だけにかかわり、辺の両端点は同じ同値類にあるので、左核は、各同値類 $C$ について「$C$ の上の値 $x|_C$ が $G[C]$ の辺について条件を満たす」ベクトルの空間 $L_C$ の直和である。各 $C$ について、$G[C]$ が二部グラフなら $\dim L_C=1$、そうでなければ $L_C=0$ であることを示せば、$\dim(\text{左核})=b(G)$ となって 3 が従う。
$C$ の頂点 $r$ を 1 つ固定する。$x\in L_C$ とし、$r$–$v$ 道 $(r=v_0,\dots,v_\ell=v)$ をとると、条件から $x_{v_i}=-x_{v_{i-1}}$ なので $x_v=(-1)^\ell x_r$ である。よって $x$ は $x_r$ で決まり、$\dim L_C\le1$ である。
$G[C]$ が二部グラフで、二部分割を $C=A\sqcup B$（$r\in A$）とする。$x_v:=1$（$v\in A$）、$x_v:=-1$（$v\in B$）と定めると、辺は $A$ と $B$ を結ぶので条件を満たし、$x\neq0$ である。よって $\dim L_C=1$ である。
逆に $0\neq x\in L_C$ があるとする。上の式から $x_r\neq0$ で、すべての $v\in C$ について $x_v\in\{x_r,-x_r\}$ である。標数が $2$ でないので $x_r\neq-x_r$ である。$A:=\{v\in C\mid x_v=x_r\}$、$B:=\{v\in C\mid x_v=-x_r\}$ とおくと $C=A\sqcup B$ であり、辺 $uw$ では $x_w=-x_u\neq x_u$ なので $u,w$ は $A$ と $B$ に分かれる。よって $G[C]$ は二部グラフである。対偶により、$G[C]$ が二部グラフでなければ $L_C=0$ である。$\square$

$S\subset E$ に、$e\in S$ で $1$、それ以外で $0$ をとるベクトル $y_S\in\mathbb{F}_2^E$ を対応させると、部分集合と $\mathbb{F}_2^E$ の元が 1 対 1 に対応し、対称差はベクトルの和に対応する。$(My_S)_v$ は $v$ に接続する $S$ の辺の本数を $2$ で割った余りなので、条件は $My_S=0$ と同値である。よって求める集合は $M$ の核であり、その次元は次元公式と thm-ccg-incidence-rank の 2 により $m-\operatorname{rank}M=m-n+c(G)$ である。$\square$