Proof. Consider the matrix \(M_G = A_G+I_n\) with coordinates \(x_{v,w}\in \mathbb{F}_2\) labeled by \(v,w\in V(G)\). We aim to compute \[\det(M_G) = \sum\limits_{\sigma\in S_n } \prod_{v\in V(G)} x_{v,\sigma(v)}.\] Let \(\sigma\in S_n\), and let \(\sigma=c_1 \dots c_k\) be its unique decomposition into disjoint cyclic permutations of length \(\geq 2\). If \(c=(v_1 \dots v_\ell)\) is a cyclic permutation, let \(\overline{c}=(v_\ell \dots v_1)\) be the reversed cyclic permutation, and define \(\overline{\sigma}=\overline{c_1}\dots\overline{c_k}\). Note that \(\overline{c}=c\) if and only if \(c\) has length \(2\), hence \(\overline{\sigma}=\sigma\) if and only if \(\sigma\) is composed of cycles of length \(\leq 2\).

Now, the term \(\prod_{v\in V(G)} x_{v,\sigma(v)}\) is equal to 1 if and only if each \(c_i\) forms a cycle in \(G\) (here single edges in \(G\) are considered cycles of length 2). Furthermore, the term corresponding to \(\sigma\) is equal to 1 if and only if the term corresponding to \(\overline{\sigma}\) is equal to 1. Therefore \[\det(M_G) = \sum\limits_{\overline{\sigma}=\sigma } \prod_{v\in V(G)} x_{v,\sigma(v)} + \sum\limits_{\overline{\sigma}\neq \sigma } \prod_{v\in V(G)} x_{v,\sigma(v)} = \sum\limits_{\overline{\sigma}=\sigma } \prod_{v\in V(G)} x_{v,\sigma(v)},\] since the summation over all \(\sigma\neq \overline{\sigma}\) must be zero by our previous observation.

Finally, if \(\sigma\) is composed of cycles of length \(\leq 2\) and its corresponding term is equal to 1, then its cycles correspond to non-adjacent edges in \(G\), i.e. \(\sigma\) defines a unique matching \(\mu\) in \(G\). Conversely, every matching \(\mu\) in \(G\) uniquely determines such a permutation \(\sigma\). Consequently, \[\det(M_G) = m(G)\pmod2.\] As \(M_G \boldsymbol{1}_n=\boldsymbol{1}_n\) implies the graph is even, the theorem statement follows. ◻

Proof. Let \(\boldsymbol{B}^{n-1}=\{B\in \boldsymbol{S}^{n-1}\colon B\mathbf{1}_{n-1} = \mathop{\mathrm{diag}}(B)\}\). We construct a bijection \(\Phi\colon \boldsymbol{E}^n \to \boldsymbol{S}^{n-2}\) by constructing two bijections \(\Phi_1: \boldsymbol{E}^n \to \boldsymbol{B}^{n-1}\) and \(\Phi_2: \boldsymbol{B}^{n-1} \to \boldsymbol{S}^{n-2}\).

Let us define \(\Phi_1\). Let \(M \in \boldsymbol{E}^n\) and write \[M = \left( \begin{array}{c|c} 1 & r^T \\\hline r & N \end{array} \right),\] where \(r\in \mathbb{F}_2^{n-1}\) and \(N\in \mathbb{F}_2^{(n-1)\times (n-1)}\). The condition \(M\mathbf{1}_n = \mathbf{1}_n\) implies that \(r^T \mathbf{1}_{n-1} = 0\) and \(r + N \mathbf{1}_{n-1} = \mathbf{1}_{n-1}\). A standard Gaussian reduction leads to \[L A L^T = \left( \begin{array}{c|c} 1 & 0 \\\hline 0 & N+rr^T \end{array} \right)\text{, where } L = \left( \begin{array}{c|c} 1 & 0 \\\hline r & I_{n-1} \end{array} \right).\] The matrix \(B= N + rr^T\) satisfies the following properties:

1. \(\det(B)=1\),

2. \(\mathop{\mathrm{diag}}(B) = \mathop{\mathrm{diag}}(N) + r = \mathbf{1}_{n-1} + r\),

3. \(B\mathbf{1}_{n-1} = (N+rr^T)\mathbf{1}_{n-1} = (\mathbf{1}_{n-1}+r) + 0 = \mathbf{1}_{n-1} + r\),

and thus \(B\in \mathcal{B}^{n-1}\). The map \(\Phi_1: M \mapsto B\) is a bijection, as \(r\) is uniquely determined as \(r = \mathop{\mathrm{diag}}(B) + \mathbf{1}_{n-1}\).

Now let us define \(\Phi_2\). Let \(B \in \mathcal{B}^{n-1}\) and write \[B = \left( \begin{array}{c|c} \alpha & y^T \\\hline y & X \end{array}\right),\] where \(X\in \boldsymbol{S}^{n-2}\). The condition \(B\mathbf{1}_{n-1} = \mathop{\mathrm{diag}}(B)\) implies that \(y + X\mathbf{1}_{n-1} = \mathop{\mathrm{diag}}(X)\). We apply the transformation \[P = \left(\begin{array}{c|c} 1 & \mathbf{1}_{n-2}^T \\\hline 0 & I \end{array}\right)\] to \(B\) to get \[B' = P B P^T = \left(\begin{array}{c|c} \gamma & (y+X\mathbf{1}_{n-2})^T \\\hline y+X\mathbf{1}_{n-2} & X \end{array}\right) = \left(\begin{array}{c|c} \gamma & \mathop{\mathrm{diag}}(X)^T \\\hline \mathop{\mathrm{diag}}(X) & X \end{array}\right)\] for some scalar \(\gamma\). We claim \(X\) is invertible. Suppose for contradiction that \(\det(X)=0\). Then there exists a non-zero \(u\) such that \(Xu=0\). For any \(v\in \mathbb{F}_2^{n-2}\) we have \(v^T X v =\mathop{\mathrm{diag}}(X)^T v\) since \(X\) is symmetric. Consequently, \(\mathop{\mathrm{diag}}(X)^T u = u^T X u = 0\). The vector \((0, u^T)^T\) then lies in the kernel of \(B'\), contradicting \(\det(B')=\det(B)=1\). We define \(\Phi_2: \boldsymbol{B}^{n-1} \to \boldsymbol{S}^{n-2}\) by \(B\mapsto X\).

Let us prove \(\Phi_2\) is a bijection by exhibiting an inverse. Given \(X \in \boldsymbol{S}^{n-2}\), we can uniquely reconstruct \(B\). Let \(\gamma = 1 + \mathop{\mathrm{diag}}(X)^T X^{-1} \mathop{\mathrm{diag}}(X)\) and let \[B' \mathrel{\vcenter{:}}= \left( \begin{array}{c|c} \gamma & \mathop{\mathrm{diag}}(X)^T \\\hline \mathop{\mathrm{diag}}(X) & X \end{array}\right),\] where our choice of \(\gamma\) makes \(B'\) invertible. Now consider \[B \mathrel{\vcenter{:}}= P^{-1} B' P^{-T}= \left(\begin{array}{c|c} \alpha & y^T \\\hline y & X \end{array}\right),\] where \(\alpha = \gamma + \mathbf{1}_{n-2}^T X \mathbf{1}_{n-2}\) and \(y = \mathop{\mathrm{diag}}(X) + X\mathbf{1}_{n-2}\). By construction, \(B\) is symmetric and our choice of \(\gamma\) ensured that \(B\) is invertible. It remains to show that the defined \(B\) satisfies the condition \(B\mathbf{1}_{n-1} = \mathop{\mathrm{diag}}(B)\). Observe that \(y + X\mathbf{1}_{n-2} = \mathop{\mathrm{diag}}(X) + X\mathbf{1}_{n-2} + X\mathbf{1}_{n-2} = \mathop{\mathrm{diag}}(X)\), so \((B\mathbf{1}_{n-1})_i = \mathop{\mathrm{diag}}(B)_i\) for \(i \geq 2\). Lastly, we need to show that \(\alpha + y^T \mathbf{1}_{n-2} = \alpha\), so it suffices to show that \(y^T \mathbf{1}_{n-2} = \mathop{\mathrm{diag}}(X)^T \mathbf{1}_{n-2} + \mathbf{1}_{n-2}^T X \mathbf{1}_{n-2} = 0\), but this holds since \(X\) is symmetric. Therefore, \(B \in \boldsymbol{B}^{n-1}\). This defines an inverse to \(\Phi_2\), hence it is a bijection. ◻

Proof. Let us denote the vertices of \(C_k\) by \(v_1,\dots,v_k\) such that \(v_iv_j\in E(C_k)\) if \(i-j = \pm 1 \pmod{k}\). Note that for any hitting set \(S\),

1. \(S\) needs to be dominating,

2. if \(v_i,v_{i+2} \in S\) then \(v_{i+1}\in S\) (where the indices are modulo \(k\)), and

3. if \(v_i,v_{i+1} \in S\) then \(v_{i+2}\in S\) (where the indices are modulo \(k\)).

If \(|S|\neq k\), then (3) implies that \(S\) is a stable set. Moreover, (1) and (2) imply that if \(v_j\notin S\) then \(|N(v_j)\cap S| =1\). By combining these remarks and centering balls of radius one at the vertices in \(S\), there must exist a packing of balls that is a cover of \(C_k\). Since each balls cover exactly \(3\) vertices, we must have that \(k\) is divisible by \(3\). If \(k\) is divisible by \(3\) then \(S=\left\{v_2,v_5,\dots,v_{k-1}\right\}\) is a hitting set. ◻

Proof of 6. Assume for contradiction that \(G\) is not extremal. Then there exists a proper hitting set \(S\subsetneq V(G)\) of \(G\). Let \(T = V(G)\setminus S\) be the nonempty set of vertices which are not hit. As \(G\) is an even graph and \(S\) is a hitting set for \(G\), for any \(s\in S\) we have \(|N(s)\cap S|\) is even, and hence \(|N(s)\cap T| = \deg(s)-|N(s)\cap S|\) is also even. Conversely, for any \(t\in T\) we have \(|N(t)\cap S|\) is odd, and hence \(|N(t)\cap T|=\deg(t)-|N(t)\cap S|\) is also odd.

Let \(H'\) be the multigraph obtained from \(G\) by adding a clique of new edges on \(N(s)\cap T\) for every \(s\in S\), and let \(H = H'\setminus S\). Color an edge \(e\in E(H)\) red if \(e\in E(H')\setminus E(G)\) and blue if \(e \in E(H')\cap E(G)\). Consider some arbitrary \(v\in V(H)\). Since \(v\in V(H) = T\), we have that \(|N_G(v)\cap S|\) is odd and \(|N_G(s)\cap T|\) is even for every \(s\in N_G(v)\cap S\). Therefore, \(v\) is incident with an odd number \[\sum_{s\in N_G(v)\cap S}(|N_G(s)\cap T|-1)\] of red edges in \(H\). Furthermore, \(v\) is incident with an odd number \(|N_G(v)\cap T|\) of blue edges in \(H\). Therefore, \(H\) is an even graph whose edges are colored red and blue so that every vertex is incident with an odd number of edges of each color, so by 2 \(H\) has an alternating red/blue cycle. Among all such cycles, choose \(C\) to be the shortest.

Let \(C = v_1,v_2,\dots,v_k,v_1\) for some even \(k\ge 2\), and assume without loss of generality that \(v_1v_2\) is a red edge. By the definition of \(H\), for any red edge \(v_iv_{i+1}\in E(C)\), \(i\in[k]\), there exists some \(s\in S\) such that \(v_i,v_{i+1}\in N_G(s)\cap T\). On the other hand, for any \(s\in S\), at most one red edge of \(C\) has both endpoints in \(N_G(s)\cap T\). To see this, assume for contradiction that there exists some \(s\in S\) and distinct \(i,j\in[k]\) such that \(v_iv_{i+1}\) and \(v_jv_{j+1}\) are both red edges in \(C\) and \(v_i, v_{i+1}, v_j, v_{j+1}\in N_G(s)\cap T\). Assume without loss of generality that \(i < j\). Since \(C\) is an alternating cycle, \(j\neq i+1\), and since \(H[N_G(s)\cap T]\) is a clique, \(v_iv_{j+1}\in E(H)\). But now the cycle \(C' = v_1,v_2,\dots,v_i,v_{j+1},\dots,v_k,v_1\) is a shorter alternating cycle in \(H\), contradicting the minimality of \(C\). Therefore, for any red edge \(v_iv_{i+1}\in E(C)\), \(i\in[k]\), there exists a unique \(s_{i,i+1}\in S\) such that \(v_i,v_{i+1}\in N_G(s_{i,i+1})\cap T\). Furthermore, by the definition of \(H\), any blue edge in \(C\) corresponds to a unique edge of \(G[T]\).

Lifting \(C\) back to \(G\), we have that \[C'' = v_1,s_{1,2},v_2,v_3,s_{3,4},v_4,\dots, v_{k-1}, s_{k-1, k}, v_kv_1\] is a cycle of length \(3k/2\) in \(G\), contradicting that \(G\) has no cycle of length divisible by \(3\). ◻

Proof. Let \(v\in V(G)\) be the vertex corresponding to the identification of \(x\) and \(y\). Assume for sake of contradiction that \(G\) is not extremal, and let \(S\subsetneq V(G)\) be a proper hitting set of \(G\). Let \(a = |N(v)\cap S\cap V(G_1)|\) and \(b = |N(v)\cap S\cap V(G_2)|\).

Case 1: \(v\notin S\). Since \(S\) is a hitting set of \(G\), we have that \(a + b\) is odd. Assume without loss of generality that \(a\) is odd and \(b\) is even. Then \(S\setminus(V(G_2)\setminus\{v\})\) is a proper hitting set of \(G_1\), contradicting that \(G_1\) is extremal.

Case 2: \(v\in S\). Since \(S\) is a hitting set of \(G\), we have that \(a + b\) is even. First assume both \(a\) and \(b\) are even. Since \(S\) is a proper hitting set of \(G\), there exists some \(u\in V(G)\setminus S\). Assume without loss of generality that \(u\in V(G_1)\). Then \(S\setminus(V(G_2)\setminus\{v\})\) is a proper hitting set of \(G_1\), contradicting that \(G_1\) is extremal. Now assume both \(a\) and \(b\) are odd. Let \(H = G[S\cap V(G_1)]\). Then \(\deg_H(v) = a\) is odd and \(\deg_H(w)\) is even for any \(w\in V(H)\setminus\{v\}\). Therefore, \(H\) is a graph with exactly one odd-degree vertex, a contradiction. ◻

Proof. Let \(G = (V, E)\), and work in the ring \(R = \mathbb{F}_2[t][x_v:v\in V]/\{x_v^2:v\in V\}\). Define the polynomial \(P = \prod_{ab\in E}(1+tx_ax_b)\in R\). For \(A\subseteq V\), write \(x^A = \prod_{a\in A}x_a\). By the definition of \(R\), we have \[P = \sum_{M\text{ matching}}t^{|M|}x^{V(M)} = \sum_{i\ge 0}\sum_{\substack{U\subseteq V\\|U|=2i}} c_Ut^ix^U,\] where \(c_U\) is the number of perfect matchings of \(G[U]\) modulo \(2\). Let \(T = V\setminus S\) and define a second polynomial \(Q = \prod_{w\in T}(1+x_w)\in R\). Consider the coefficient \([t^kx^V](P Q)\). Any \(U\subseteq V\) with \(|U| \neq 2k\) cannot contribute to this coefficient as its monomial misses \(t^k\). Any \(U\subseteq V\) with \(U\not\supseteq S\) cannot contribute to this coefficient as its monomial misses \(x_s\) for some \(s\in S\). Any \(U\subseteq V\) with \(|U|=2k\) and \(U\supseteq S\) contributes \(c_U\) to this coefficient exactly once: choose “\(1\)” for \(w\in T\cap U\) and “\(x_w\)” for \(w\in T\setminus U\) when multiplying by \(Q\). Therefore, \[[t^kx^V](P Q) = \sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S}} c_U = m_k(G, S),\] where \(m_k(G, S)\) is the number of size-\(k\) matchings covering \(S\) modulo \(2\). For each \(v\in V\), define the differential operator \(\partial_v\) with \(\partial_v(x_v) = 1\), \(\partial_v(x_u) = 0\) for \(u\neq v\), and \(\partial_v(t) = 0\). Define \(\partial = \sum_{v\in V}\partial_v\). For each \(v\in V\), using the fact that \((1+tx_u x_v)^2 = 1\), the product rule gives \[\partial_v P = \partial_v\prod_{ab\in E}(1+tx_ax_b) = \sum_{u\in N(v)}tx_uP(1+tx_ux_v) = tP\sum_{u\in N(v)}x_u.\] Summing over all \(v\in V\) and using \(\deg(v) = 0\) modulo \(2\) as \(G\) is even, \[\partial P = tP\sum_{v\in V}\sum_{u\in N(v)}x_u = tP\sum_{v\in V}\deg(v)x_v = 0.\] Now consider the coefficient \([t^kx^V]\partial(P Q)\). Since \(\partial\) reduces the degrees of all monomials by \(1\), it must be that \([t^kx^V]\partial(P Q) = 0\). On the other hand, expanding \(\partial(P Q)\) with the product rule and using \(\partial P=0\), \[\partial(P Q) = (\partial P) Q + P(\partial Q) = P(\partial Q).\] Since \(Q = \prod_{w\in T}(1+x_w)\), we have \(\partial Q = Q\sum_{w\in T}(1+x_w) = Q(|T| + \sum_{w\in T}x_w)\). Hence \(\partial (P Q) = P Q(|T| + \sum_{w\in T}x_w)\). Gathering coefficients, this gives \[[t^kx^V]\partial(P Q) = |T|m_k(G, S) + \sum_{w\in T}[t^kx^{V\setminus\{w\}}](P Q).\] Now fix \(w\in T\) and consider the coefficient \([t^kx^{V\setminus\{w\}}](PQ)\). The same reasoning for determining \([t^k x^V](PQ)\) yields that any \(U\subseteq V\) with \(|U| \neq 2k\) or \(U\not\supseteq S\) cannot contribute to this coefficient. Furthermore, any \(U\) with \(w\in U\) also cannot contribute, since it cannot have \(x_w\) in its monomial. Finally, any \(U\subseteq V\) with \(|U|=2k\), \(U\supseteq S\), and \(U\not\ni w\) contributes \(c_U\) to this coefficient exactly once: choose “\(1\)” for the vertices in \(T\cap U\) and \(w\), and choose \(x_a\) for \(a\in T\setminus U\) when multiplying by \(Q\). Therefore, \[[t^kx^{V\setminus\{w\}}](P Q) = \sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S\\U\not\ni w}} c_U\] is the number of size-\(k\) matchings covering \(S\) but not covering \(w\). Summing over all \(w\in T\) and interpreting the scalars \(|S|\), \(|T|\), \(|U|\), and \(|V|\) modulo \(2\), \[\begin{align} \sum_{w\in T}[t^kx^{V\setminus\{w\}}](P Q) &= \sum_{w\in T}\sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S\\U\not\ni w}} c_U = \sum_{w\in T}\sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S}} \mathbb{1}[w\notin U]c_U\\ &= \sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S}}c_U|T\setminus U| = \sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S}}c_U(|V|-|U|)\\ &= \sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S}}c_U(|V|-2k) = |V|\sum_{\substack{U\subseteq V\\|U|=2k\\U\supseteq S}}c_U = |V|m_k(G, S). \end{align}\] It follows that \(0 = [t^kx^V]\partial(P Q) = |T|m_k(G, S) + |V|m_k(G, S) = (|V|-|T|)m_k(G,S) = |S|m_k(G,S)\). Since \(|S|\) is odd, this means \(m_k(G,S) = 0\), so the number of size-\(k\) matchings covering \(S\) is even. ◻

Proof of Lemma 4.. Let \(G_1 = G[A]\) and \(G_2 = G[B]\). Suppose for contradiction that, without loss of generality, \(G_1\) is not extremal. Since \(G\) is an even graph, it must be that \(G_1\) and \(G_2\) are even graphs. Indeed, for \(i\in [2]\) and \(u \in V(G_i)\setminus\{v\}\), we have \(\deg_{G_i}(u) = \deg_G(u)\) is even. This further implies that \(\deg_{G_i}(v)\) is even, as otherwise \(G_i\) would have exactly one vertex of odd degree, a contradiction.

As \(G\) is extremal, by Theorem 1 we have \(m(G)\) is odd. Any matching in \(G\) either covers \(v\) via an edge in \(G_1\), covers \(v\) via an edge in \(G_2\), or does not cover \(v\). Since there are no edges from \(A\setminus B\) to \(B\setminus A\), \[\begin{align} m(G) &= m(G_1\setminus v)\cdot m(G_2\setminus v) + m(G_1, v)\cdot m(G_2\setminus v) + m(G_1\setminus v)\cdot m(G_2, v) \\&= m(G_2\setminus v)[m(G_1\setminus v) + m(G_1, v)] + m(G_1\setminus v)\cdot m(G_2,v) \\&= m(G_2\setminus v)\cdot m(G_1) + m(G_1\setminus v)\cdot m(G_2, v). \end{align}\] Since \(G_1\) is not extremal, \(m(G_1)\) is even, so \(m(G)\) has the same parity as \(m(G_1\setminus v)\cdot m(G_2, v)\). However, by Corollary 1 we have \(m(G_2, v)\) is even, so \(m(G)\) must also be even, a contradiction. ◻

Proof. In the following, all sums will be taken modulo \(2\). Let \(e=xy\in E(G)\) and let \(G'\) be the graph obtained by subdividing \(e\) three times, introducing the path \(x-a-b-c-y\). Let us relate the total number of matchings in \(G'\) with the one in \(G\). For \(I\subseteq\{xa,ab,bc,cy\}\), we define \(K_I\) as the number of matching \(M\) on \(G'\) such that \(M\cap \{xa,ab,bc,cy\} = I\). We have that \[\begin{align} m(G') &= K_\varnothing + K_{xa}+ K_{xa,bc} + K_{cy}+ K_{ab,cy} + K_{ab} + K_{bc} + K_{xa,cy}\\ &= K_\varnothing + K_{xa}+ K_{xa} + K_{cy}+ K_{cy} + K_{ab} + K_{ab} + K_{xa,cy}\\ &= K_\varnothing + K_{xa,cy}. \end{align}\] Notice that the \(K_{xa,cy}\) is the number of matches on \(G\) that includes \(e\). Similarly, \(K_\varnothing\) is equivalent to the number of matchings of \(G\) not including \(e\). Therefore, \[\begin{align} m(G') &=K_\varnothing + K_{xa,cy}\\ &= m(G-e) + m(G,e)\\ &= m(G). \end{align}\] 1 lets us conclude. ◻

Proof. Work modulo \(2\) throughout. Clearly \(G\) is even if and only if \(G_1\) and \(G_2\) are even. Let \(H\) be the bipartite subgraph of \(G\) with \(V(H) = X_1\cup X_2\) and \(E(H) = E(X_1,X_2)\) (the edges added in the completion operation). Let \(\mathcal{M}\) be the set of matchings of \(H\). Since there are no edges from \(V(G_1)\) to \(V(G_2)\) except those in \(E(H)\), \[m(G) = \sum_{M\in \mathcal{M}} m(G_1\setminus V(M)) \cdot m(G_2\setminus V(M)).\] We will group the terms of this summation into three: the empty matching, matchings of size exactly one, and matchings of size at least two. The latter two will be shown to contribute zero to the sum. We have: \[m(G) = m(G_1)\cdot m(G_2) + \sum_{u\in X_1, v\in X_2} m(G_1\setminus u) \cdot m(G_2\setminus v) + \sum_{\substack{M\in \mathcal{M}\\ |M| \geq 2}} m(G_1\setminus V(M)) \cdot m(G_2\setminus V(M)).\] By 1, for any \(u\in X_1\), we have \(m(G_1\setminus u) = m(G_1) - m(G_1,u) = m(G_1)\). Similarly, for any \(v\in X_2\), we have \(m(G_2\setminus v) = m(G_2)\). Therefore, \[m(G) = m(G_1)\cdot m(G_2) + |E(X_1,X_2)| \cdot m(G_1)\cdot m(G_2) + \sum_{\substack{M\in \mathcal{M}\\ |M| \geq 2}} m(G_1\setminus V(M)) \cdot m(G_2\setminus V(M)).\] Since \(|X_1|\) and \(|X_2|\) are even, \(|E(X_1,X_2)| = 0\), so this simplifies to \[m(G) = m(G_1)\cdot m(G_2) + \sum_{\substack{M\in \mathcal{M}\\ |M| \geq 2}} m(G_1\setminus V(M)) \cdot m(G_2\setminus V(M)).\] Consider some arbitrary \(2\le k\le \min(|X_1|,|X_2|)\). Let \(V_i\subseteq X_i\) be sets of size \(k\) for \(i\in[2]\). Then the number of matchings \(M\) in \(\mathcal{M}\) with \(V(M) = V_1\cup V_2\) is exactly \(k!\), which is \(0\) modulo \(2\). Grouping matchings by \(|M|\), \[\sum_{\substack{M\in \mathcal{M}\\ |M| \geq 2}} m(G_1\setminus V(M)) \cdot m(G_2\setminus V(M)) = \sum_{k=2}^{\min(|X_1|,|X_2|)} \sum_{\substack{V_1 \subseteq X_1,\\ V_2 \subseteq X_2,\\ |V_1|=|V_2|=k}} k! \cdot m(G_1\setminus V_1) \cdot m(G_2\setminus V_2) = 0.\] Therefore, \(m(G) = m(G_1)\cdot m(G_2)\), so over \(\mathbb{F}_2\) we have \(m(G) = 1\) if and only if \(m(G_1) = 1\) and \(m(G_2)=1\). By 1, it follows that \(G\) is extremal if and only if \(G_1\) and \(G_2\) are extremal. ◻

Proof. (\(\implies\)) Suppose \(G\) is extremal. Suppose by contradiction that \(G'\) admits a proper hitting set \(S' \subseteq V(G')\). We claim that \(S = S' \setminus \{w_1,\ldots,w_k\} \subseteq V(G)\) is a hitting set for \(G\).

Consider any \(v_i\) in \(G'\) and suppose \(v_i\) is hit. Consider the pair of vertices \(\{v_{i-1},w_{i-1}\}\). To ensure that \(w_{i-1}\) is toggled, it must be the case that either both or neither of them are hit. The same is true for the pair \(\{w_i,v_{i+1}\}\). On reversing the sun-cycle operation to obtain \(G\), it is easy to see that the parity of \(v_i\) is preserved.

Now suppose \(v_i\) is not hit. To ensure that \(w_{i-1}\) and \(w_i\) are toggled, it must be the case that exactly one of \(\{v_{i-1},w_{i-1}\}\) and exactly one of \(\{w_i,v_{i+1}\}\) has been hit. Reversing the sun-cycle operation to obtain \(G\), the parity of \(v\) is again preserved.

So it follows that \(S\) is a hitting set for \(G\). Since \(G\) is extremal, it must be the case that \(S = V(G)\). Since \(S'\) is a hitting set for \(G'\) and each \(w_i\) has exactly two hit neighbors in \(V(G)\), it must be the case that \(w_i\) is also hit. It follows that \(S' = V(G')\), a contradiction.

(\(\impliedby\)) Suppose \(G'\) is extremal. Suppose for contradiction that \(G\) admits a proper hitting set \(S\). Then set \(S' = S \cup \{w_i \colon v_i, v_{i+1} \in S\}\). By similar parity arguments as the previous direction, \(S'\) is a hitting set for \(G'\), which implies that \(S' = V(G')\) and in turn forces \(S = V(G)\), a contradiction. ◻