Proof. We first prove (1). Since \(F\) is an essential disconnecting set, at least two components of \(G-F\) contain edges. Let \(C\) be one such component. Since another component of \(G-F\) contains an edge, the cut \(\delta_G(V(C))\) is essential. Moreover, \(\delta_G(V(C))\subseteq F\), because every edge from \(C\) to \(V(G)\setminus V(C)\) must have been deleted by \(F\). Since \(G\) is essentially \(2\)-edge-connected, \[2\le |\delta_G(V(C))|\le |F|=2.\] Thus \(\delta_G(V(C))=F\). In particular, every edge of \(F\) has one end in \(C\) and one end outside \(C\).

Let \(C'\) be another component of \(G-F\) containing an edge. The same argument gives \(\delta_G(V(C'))=F\). Hence every edge of \(F\) joins \(C\) to \(C'\). Since \(G\) is connected, there can be no third component of \(G-F\). Therefore \(G-F\) has exactly two components, and \(F\) is an edge-cut.

Now assume further that \(G\) is subcubic and \(2\)-edge-connected. Let the two components of \(G-F\) have vertex sets \(S\) and \(V(G)\setminus S\), so that \(F=\delta_G(S)\). Suppose, for a contradiction, that the two edges of \(F\) have a common end \(u\in S\). Since \(G\) is subcubic, \(u\) has at most one neighbor in \(S\). As \(G\) is connected and \(S\setminus\{u\}\) is nonempty, \(u\) has exactly one neighbor in \(S\), say \(u'\). Then the only edge from \(S\setminus\{u\}\) to \(V(G)\setminus (S\setminus\{u\})\) is \(uu'\). Hence \(uu'\) is a bridge of \(G\), contradicting that \(G\) is \(2\)-edge-connected. The same argument applies if the common end lies in \(V(G)\setminus S\). Therefore \(F\) is a matching. This proves (1).

We now prove (2). Since \(F\) is a cyclic disconnecting set, at least two components of \(G-F\) contain cycles. Let \(C\) be one such component. Since another component of \(G-F\) contains a cycle, the cut \(\delta_G(V(C))\) is cyclic. Moreover, \(\delta_G(V(C))\subseteq F\). Since \(G\) is cyclically \(3\)-edge-connected, \[3\le |\delta_G(V(C))|\le |F|=3.\] Thus \(\delta_G(V(C))=F\). In particular, every edge of \(F\) has one end in \(C\) and one end outside \(C\).

Let \(C'\) be another component of \(G-F\) containing a cycle. The same argument gives \(\delta_G(V(C'))=F\). Hence every edge of \(F\) joins \(C\) to \(C'\). Since \(G\) is connected, there can be no third component of \(G-F\). Therefore \(G-F\) has exactly two components, and \(F\) is an edge-cut.

It remains to prove the matching statement under the additional assumption that \(G\) is subcubic. Let the two components of \(G-F\) have vertex sets \(S\) and \(V(G)\setminus S\), so that \(F=\delta_G(S)\). Suppose, for a contradiction, that two edges of \(F\) have a common end \(u\in S\). Let \(r=d_G(u,V(G)\setminus S)\). Then \(r\ge 2\). Since \(G\) is subcubic, \(d_G(u,S)\le 1\). Hence no cycle of \(G[S]\) uses \(u\).

Put \(S'=S\setminus\{u\}\). Then \[|\delta_G(S')| = |\delta_G(S)|-r+d_G(u,S) \le 3-2+1 =2.\] Both sides of this new cut still contain cycles: the side \(S'\) contains a cycle because \(G[S]\) contains a cycle and no cycle of \(G[S]\) uses \(u\), while the other side already contained a cycle before \(u\) was moved. Thus \(\delta_G(S')\) is a cyclic edge-cut of size less than \(3\), contradicting that \(G\) is cyclically \(3\)-edge-connected.

The same argument applies if two edges of \(F\) have a common end in \(V(G)\setminus S\). Therefore no two edges of \(F\) share an end, and so \(F\) is a matching. This proves (2). ◻

Proof. We first choose the cut carefully. Let \(F=\{u_1u_2,v_1v_2\}\) be an essential \(2\)-edge-cut of \(G\). By Lemma 5(1), \(G-F\) has exactly two components and \(F\) is a matching in \(G\). Let \(H_1\) and \(H_2\) be these two components, where \(u_i,v_i\in V(H_i)\) for each \(i\in [2]\). Then \(u_1\ne v_1\) and \(u_2\ne v_2\) since \(F\) is a matching.

For each \(i\in [2]\), let \(H_i^*\) be obtained from \(H_i\) by adding two pendant edges at \(u_i\) and \(v_i\). A coloring of \(H_i^*\) is called a same-state coloring if the two pendant edges receive the same color, and a different-state coloring if they receive distinct colors.

Since \(F\) is essential, each component \(H_i\) contains an edge. Hence, for each \(i\in [2]\), the graph \(H_i^*\) has at least one state: delete an edge from the other component and restrict a proper edge \(3\)-coloring of the resulting graph to the \(H_i\)-side.

The two sides cannot have a common state. Indeed, if both \(H_1^*\) and \(H_2^*\) had same-state colorings, or both had different-state colorings, then after permuting colors on one side, the two colorings could be glued along the two edges of \(F\), giving a proper edge \(3\)-coloring of \(G\), a contradiction.

Thus the two state sets are nonempty and disjoint subsets of \(\{\text{same},\text{different}\}\). Therefore one side has only same-state colorings and the other has only different-state colorings. Among all essential \(2\)-edge-cuts of \(G\), choose \(F\) so that the same-state side is as large as possible. We keep the notation so that \(H_1^*\) has only same-state colorings and \(H_2^*\) has only different-state colorings.

We claim that \(u_2v_2\notin E(H_2)\). Suppose, to the contrary, that \(u_2v_2\in E(H_2)\). Since \(H_2^*\) has only different-state colorings, each of \(u_2\) and \(v_2\) has a neighbor in \(H_2-\{u_2,v_2\}\). Indeed, if, say, \(u_2\) were incident in \(H_2\) only with \(u_2v_2\), then from a different-state coloring of \(H_2^*\) we could recolor the pendant edge at \(u_2\) with the color of the pendant edge at \(v_2\), obtaining a same-state coloring of \(H_2^*\), a contradiction.

Let \(u_2u_2'\) and \(v_2v_2'\) be edges from \(\{u_2,v_2\}\) to \(H_2-\{u_2,v_2\}\). We first show that \(u_2'\ne v_2'\). Suppose not, and write \(u_2'=v_2'=z\). Then \(u_2v_2zu_2\) is an independent triangle, contradicting the assumption that \(G\) has no independent triangle. Hence \(u_2'\ne v_2'\).

Since \(\Delta(G)\le 3\), the edges \(u_2u_2'\) and \(v_2v_2'\) are the only edges from \(\{u_2,v_2\}\) to \(H_2-\{u_2,v_2\}\). Thus \[F'=\{u_2u_2',v_2v_2'\}\] is an edge-cut. Moreover, \(F'\) is essential. After deleting \(F'\), one component contains \(H_1\) together with \(u_2,v_2\) and the edges \(u_1u_2,v_1v_2,u_2v_2\), so this component contains an edge. The other side contains \(u_2'\) and \(v_2'\). Since \(u_2'\ne v_2'\) and \(\delta(G)\ge 2\), the vertex \(u_2'\) has an incident edge different from \(u_2u_2'\). This edge lies in \(H_2-\{u_2,v_2\}\), since \(v_2\) is adjacent to \(v_2'\) rather than \(u_2'\). Hence the other side also contains an edge. Therefore \(F'\) is an essential \(2\)-edge-cut.

Let \(H_1'\) be the component of \(G-F'\) containing \(H_1\). Thus \(H_1'\) is obtained from \(H_1\) by adding \(u_2,v_2\) and the edges \(u_1u_2,v_1v_2,u_2v_2\).

We show that \((H_1')^*\) has only same-state colorings. Consider any proper edge \(3\)-coloring of \((H_1')^*\). Restrict it to the old \(H_1\)-side, viewing \(u_1u_2\) and \(v_1v_2\) as the two pendant edges of \(H_1^*\). Since \(H_1^*\) has only same-state colorings, the edges \(u_1u_2\) and \(v_1v_2\) receive the same color, say \(\alpha\). At the vertices \(u_2\) and \(v_2\), the edge \(u_2v_2\) must receive a color different from \(\alpha\). Therefore the two new pendant edges of \((H_1')^*\) must both receive the third color. Thus every coloring of \((H_1')^*\) has same state. This contradicts the maximal choice of the same-state side, since \(H_1'\) properly contains \(H_1\). Hence \(u_2v_2\notin E(H_2)\).

Now let \(x\) be a new vertex, and define \[G_1=H_1+xu_1+xv_1 \qquad\text{and}\qquad G_2=H_2+u_2v_2,\] where \(u_2v_2\) is a new edge. This is well-defined and both graphs are simple because \(u_1 \ne v_1\), \(u_2\ne v_2\), and \(u_2v_2\notin E(H_2)\).

We claim that \(G_1\) and \(G_2\) are \(3\)-critical. First, neither graph is edge \(3\)-colorable. If \(G_1\) had a proper edge \(3\)-coloring, then the two edges incident with \(x\) would receive distinct colors. Deleting \(x\) would give a different-state coloring of \(H_1^*\), a contradiction. Similarly, if \(G_2\) had a proper edge \(3\)-coloring, then replacing the edge \(u_2v_2\) by two pendant edges with the same color would give a same-state coloring of \(H_2^*\), a contradiction.

It remains to show that deleting any edge from either graph gives an edge \(3\)-colorable graph. For \(G_1\), if \(e\) is one of the two edges incident with \(x\), then a same-state coloring of \(H_1^*\) gives a proper edge \(3\)-coloring of \(G_1-e\). If \(e\in E(H_1)\), then \(G-e\) has a proper edge \(3\)-coloring. Restricting this coloring to the \(H_2\)-side gives a state coloring of \(H_2^*\), hence a different-state coloring. Therefore the restriction to \(H_1-e\) gives a different-state coloring of \(H_1^*-e\), which extends to a proper edge \(3\)-coloring of \(G_1-e\) by using the two distinct boundary colors on \(xu_1\) and \(xv_1\).

For \(G_2\), if \(e=u_2v_2\), then \(G_2-e=H_2\) is \(3\)-colorable by deleting the pendant edges from any coloring of \(H_2^*\). If \(e\in E(H_2)\), then \(G-e\) has a proper edge \(3\)-coloring. Restricting this coloring to the \(H_1\)-side gives a state coloring of \(H_1^*\), hence a same-state coloring. Therefore the restriction to \(H_2-e\) gives a same-state coloring of \(H_2^*-e\), and replacing the two pendant edges by the single edge \(u_2v_2\) with their common color gives a proper edge \(3\)-coloring of \(G_2-e\).

Thus \(G_1\) and \(G_2\) are \(3\)-critical.

Finally, \(G\) is obtained as the Hajós join of \(G_1\) and \(G_2\): delete the edge \(xv_1\) from \(G_1\), delete the edge \(u_2v_2\) from \(G_2\), identify \(x\) with \(u_2\), and add the edge \(v_1v_2\). The remaining edge \(xu_1\) becomes \(u_1u_2\), so the resulting graph is exactly \(G\).

Since \(G\) is nontrivial, it has at least three vertices of degree \(2\). Suppose, for a contradiction, that both \(G_1\) and \(G_2\) are trivial. Then each has exactly one vertex of degree \(2\). In \(G_1\), the new vertex \(x\) has degree \(2\), so \(x\) is the unique degree-\(2\) vertex of \(G_1\). In the Hajós-join described above, the vertex \(x\) is identified with \(u_2\) and does not remain as a separate vertex. All vertices of \(G_1-x\) keep their degrees, and the vertices of \(G_2\) keep their degrees after deleting \(u_2v_2\) and adding \(v_1v_2\). Hence the resulting graph has at most two vertices of degree \(2\). This contradicts that \(G\) has at least three vertices of degree \(2\). Therefore at least one of \(G_1\) and \(G_2\) is nontrivial. ◻

Proof. First note a simple consequence of the assumptions on \(H\). Since \(H\) is class \(1\), \(H\) has a proper edge \(3\)-coloring. Since \(H\) has exactly three vertices of degree \(2\) and all other vertices have degree \(3\), we have \(|V(H)|\) odd. In any proper edge \(3\)-coloring of \(H^p\), the colors on \(e_1,e_2,e_3\) are precisely the colors missing at \(x_1,x_2,x_3\) in the restriction to \(H\). Hence, by the Parity Lemma (Lemma 4), in every proper edge \(3\)-coloring of \(H^p\), the pendant edges \(e_1,e_2,e_3\) receive three distinct colors.

We first show that \(J\) is not edge \(3\)-colorable. Suppose, to the contrary, that \(J\) has a proper edge \(3\)-coloring. Restrict this coloring to \(H\) and view the three edges \(y_i x_{\sigma(i)}\) as the pendant edges \(e_{\sigma(i)}\) of \(H^p\). By the preceding paragraph, these three edges receive three distinct colors. Now restrict the same coloring to \(D=G-y\) and view the three edges \(y_i x_{\sigma(i)}\) as the pendant edges \(f_i\) of \(D^p\). Then \(f_1,f_2,f_3\) receive three distinct colors, so we can replace them by the three edges \(yy_1,yy_2,yy_3\) and obtain a proper edge \(3\)-coloring of \(G\), a contradiction. Hence \(J\) is class \(2\).

It remains to show that deleting any edge of \(J\) gives an edge \(3\)-colorable graph. We consider three cases.

First let \(e\in E(G-y)\). Since \(G\) is \(3\)-critical, \(G-e\) has a proper edge \(3\)-coloring. At the vertex \(y\), the three edges \(yy_1,yy_2,yy_3\) receive three distinct colors. Deleting \(y\) and replacing these three edges by the pendant edges \(f_1,f_2,f_3\) gives a proper edge \(3\)-coloring of \(D^p-e\) in which \(f_1,f_2,f_3\) receive three distinct colors. Also, as shown above, \(H^p\) has a proper edge \(3\)-coloring in which \(e_1,e_2,e_3\) receive three distinct colors. After a permutation of colors, these two colorings agree on the identified pendant edges. Hence they combine to give a proper edge \(3\)-coloring of \(J-e\).

Next let \(e=y_i x_{\sigma(i)}\) be one of the three new edges. Since \(G\) is \(3\)-critical, \(G-yy_i\) has a proper edge \(3\)-coloring. The two edges \(yy_j,yy_k\), where \(\{i,j,k\}=[3]\), receive distinct colors. Deleting \(y\) gives a coloring of \(G-y\) in which the two remaining new edges should receive two distinct prescribed colors. On the \(H\)-side, take a proper edge \(3\)-coloring of \(H^p\) in which \(e_1,e_2,e_3\) receive three distinct colors, delete the pendant edge \(e_{\sigma(i)}\), and permute the colors so that \(e_{\sigma(j)}\) and \(e_{\sigma(k)}\) receive the prescribed colors. These two colorings combine to give a proper edge \(3\)-coloring of \(J-e\).

Finally let \(e\in E(H)\). We use compatibility.

If Type I holds, then \(\mathcal{S}_H(e)\neq\emptyset\); choose a pair \(Q_0\in \mathcal{S}_H(e)\). Since \(\mathcal{S}_D\) contains all three pairs, the corresponding pair \(P=\{f_i:e_{\sigma(i)}\in Q_0\}\) is realized in \(D^p\).

If Type II holds, then \(|\mathcal{S}_D|=2\) and \(|\mathcal{S}_H(e)|\ge 2\). Under the bijection \(\sigma\), the two pairs in \(\mathcal{S}_D\) correspond to two pairs of \(\{e_1,e_2,e_3\}\). Since two families of two \(2\)-subsets of a \(3\)-element set must intersect, there is a pair \(Q_0\in \mathcal{S}_H(e)\) whose corresponding pair \(P=\{f_i:e_{\sigma(i)}\in Q_0\}\) lies in \(\mathcal{S}_D\).

In either Type I or Type II, choose a coloring of \(D^p\) realizing \(P\) and a coloring of \(H^p-e\) realizing \(Q_0\). After a permutation of colors on one side, the colors on the identified pendant edges agree. Hence the two colorings combine to give a proper edge \(3\)-coloring of \(J-e\).

It remains to consider Type III. In this case, both \(D^p\) and \(H^p-e\) have monochromatic states. Choose such colorings. After a permutation of colors on one side, all three pendant edges on both sides receive the same color. Hence the two colorings agree on the identified pendant edges, and they combine to give a proper edge \(3\)-coloring of \(J-e\).

Finally, \(J\) is nontrivial. Indeed, the vertex \(y\) has degree \(3\) in \(G\), and the operation replaces \(y\) by the graph \(H\) while preserving the degrees of all vertices of \(G-y\). Hence all degree-\(2\) vertices of \(G\) remain degree-\(2\) vertices of \(J\). Since \(G\) is nontrivial, \(J\) has at least three degree-\(2\) vertices. ◻

Proof. By Lemma 5(2), \(G'-F\) has exactly two components and \(F\) is a matching in \(G'\).

We prove the degree assertion for \(H\). Since \(H\) contains no vertex that has degree \(2\) in \(G'\), and since \(G'\) is subcubic and \(3\)-critical, every vertex of \(H\) has degree \(3\) in \(G'\). Since \(F\) is a matching in \(G'\), each vertex \(x_i\) is incident with exactly one edge of \(F\). Thus \(d_H(x_i)=2\) for each \(i\in[3]\). Every other vertex of \(H\) is incident with no edge of \(F\), and therefore has degree \(3\) in \(H\). Thus \(H\) has exactly three vertices of degree \(2\), namely \(x_1,x_2,x_3\), and all other vertices of \(H\) have degree \(3\). Also, \(H\) is connected because it is a component of \(G'-F\).

We show that \(H\) is class \(1\). Choose an edge \(g\in F\). Since \(G'\) is \(3\)-critical, \(G'-g\) has a proper edge \(3\)-coloring. Restricting this coloring to \(H\) gives a proper edge \(3\)-coloring of \(H\). Hence \(H\) is class \(1\). This proves (1).

We now prove that \(G\) is a nontrivial \(3\)-critical graph. The subgraph \(H\) is an induced proper subgraph of \(G'\), since it is a component of \(G'-F\). Moreover, \(H\) has odd order (the number of vertices of odd degree in \(H\) is even and it has exactly three vertices of even degree) with \(\mathop{\mathrm{def}}(H)=\sum_{v\in V(H)}(3-d_H(v))=3\). Thus Lemma 6 applies with \(k=3\), and the graph \(G\) obtained by contracting \(H\) is \(3\)-critical.

It remains to check that \(G\) is nontrivial. Since \(G'\) is nontrivial, \(G'\) has at least three vertices of degree \(2\). By assumption, no vertex of \(H\) has degree \(2\) in \(G'\). Hence all degree-\(2\) vertices of \(G'\) lie outside \(H\), and their degrees are unchanged when \(H\) is contracted. Thus \(G\) has at least three vertices of degree \(2\), and so \(G\) is nontrivial. This proves (2).

By the definition of \(G\), the vertex \(y\) has neighbors \(y_1,y_2,y_3\) in \(G\). Moreover, \(G'\) is obtained from \(G-y\) and \(H\) by adding the three edges \(y_i x_i\) for \(i\in[3]\). Thus \(G'\) is the Meredith-type extension of \(G\) through \(H\) at \(y\). This proves (3).

We first note that \(D^p\) has no rainbow boundary state. Indeed, if \(D^p\) had a proper edge \(3\)-coloring in which \(f_1,f_2,f_3\) received three distinct colors, then identifying the three pendant ends into a single vertex would give a proper edge \(3\)-coloring of \(G\), contradicting that \(G\) is class \(2\).

For (4), fix \(i\in[3]\), and let \(\{i,j,k\}=[3]\). Since \(G\) is \(3\)-critical, \(G-yy_i\) has a proper edge \(3\)-coloring. The two edges \(yy_j\) and \(yy_k\) receive distinct colors. Deleting \(y\) and replacing \(yy_j,yy_k\) by the pendant edges \(f_j,f_k\), and then coloring \(f_i\) with a color missing at \(y_i\), gives a proper edge \(3\)-coloring of \(D^p\). Since \(f_j\) and \(f_k\) receive distinct colors, and since \(D^p\) has no rainbow boundary state, the color on \(f_i\) must agree with exactly one of the colors on \(f_j\) and \(f_k\). Hence \(D^p\) realizes a pair state involving \(f_i\). Since this holds for every \(i\in[3]\), the graph \(D^p\) realizes at least two pair states. This proves (4).

For (5), let \(e\in E(H)\). Since \(G'\) is \(3\)-critical, \(G'-e\) has a proper edge \(3\)-coloring. Restricting this coloring to the two sides of the cut gives a proper edge \(3\)-coloring of \(D^p\) and a proper edge \(3\)-coloring of \(H^p-e\). These two colorings have the same boundary state on the three cut edges, with \(f_i\) corresponding to \(e_i\) for each \(i\in[3]\). This common state cannot be a rainbow state, since \(D^p\) has no rainbow boundary state. Therefore the common state is either a pair state or a monochromatic state. In the first case, \(D^p\) and \(H^p-e\) have a common pair state. In the second case, both \(D^p\) and \(H^p-e\) have a common monochromatic state. This proves (5). ◻

Proof of Theorem 1. Let \(G\) be an \(n\)-vertex nontrivial \(3\)-critical graph.

If \(G\) contains an independent triangle \(T\), then by Lemma 7 the graph \(G'\) obtained from \(G\) by contracting \(T\) to a single vertex \(x\) is \(3\)-critical. Moreover, \(G'\) is nontrivial, since the independent triangle can have at most one vertex that has degree 2 in \(G\) by Vizing’s Adjacency Lemma and in that case, the new contracted vertex also has degree 2. Thus \(G\) is obtained from \(G'\) by a vertex-blowup at \(x\), and Statement (a) holds.

Suppose next that \(G\) contains a triangle \(xyzx\) that is not independent in \(G\). Since \(\Delta(G)=3\) and \(G\ne K_4\), there is a vertex \(w\in V(G)\setminus\{x,y,z\}\) adjacent to exactly two vertices of the triangle; say \(wx,wy\in E(G)\). Let \[F=\delta_G(\{x,y,z,w\}).\] The vertices \(x\) and \(y\) already have degree \(3\), and only \(z\) and \(w\) can send edges to \(V(G)\setminus\{x,y,z,w\}\). Hence \(|F|\le 2\). Since \(G\) is connected and has no bridge, and since \(G\) is nontrivial, the set \(V(G)\setminus\{x,y,z,w\}\) is nonempty and \(|F|\ne 0,1\). Thus \(|F|=2\). Consequently both \(z\) and \(w\) have degree \(3\). Since \(G\) is 2-edge-connected and \(|F|=2\), it follows that \(G-F\) has exactly two components. Since \(G\) is nontrivial, all degree-\(2\) vertices of \(G\) lie in the other component of \(G-F\); in particular, that component has at least three vertices and contains an edge. The set \(\{x,y,z,w\}\) also induces a subgraph containing a cycle. Hence \(F\) is an essential \(2\)-edge-cut. By Lemma 9, the graph \(G\) is obtained from two smaller \(3\)-critical graphs by a Hajós-join, at least one of which is nontrivial. The same conclusion holds if \(G\) has any cyclic \(2\)-edge-cut. In either case Statement (b) holds.

We may therefore assume that \(G\) has girth at least \(4\) and is cyclically \(3\)-edge-connected.

Suppose that \(G\) has a cyclic \(3\)-edge-cut \(F\) such that one component \(H\) of \(G-F\) contains no vertex of degree \(2\) in \(G\). By Lemma 11(2), contracting \(H\) to a single vertex yields a \(3\)-critical graph \(G'\), and \(G\) is recovered from \(G'\) by a Meredith-type extension at that vertex by Lemma 11(3). The graph \(G'\) has at least three vertices of degree 2. Indeed, all degree-\(2\) vertices of \(G\) lie outside \(H\), and so they remain in \(G'\), and so \(G'\) is nontrivial. Thus Statement (c) holds.

Finally, assume that \(G\) has girth at least \(4\), is cyclically \(3\)-edge-connected, and that for every cyclic \(3\)-edge-cut \(F\) each component of \(G-F\) contains a vertex of degree \(2\) in \(G\). By Lemma 12, \(G\) can be completed to a snark \(\widehat G\). The completion described in Lemma 12 gives Statement (d) when \(n\) is odd and Statement (e) when \(n\) is even. ◻

Proof of Corollary 2. Suppose, for a contradiction, that the theorem is false, and choose a \(3\)-critical graph \(G\) of even order \(n<18\) with \(n\) minimum.

First suppose that \(G\) is trivial. Then \(G\) contains a \(3\)-overfull subgraph \(H\). Since \(G\) is edge-critical, \(H=G\); otherwise, deleting an edge of \(G\) outside \(H\) would leave the same overfull subgraph and hence would still be class \(2\), contradicting criticality. Thus \(G\) itself is overfull. But a subcubic overfull graph has odd order and exactly one vertex of degree \(2\), a contradiction. Hence \(G\) is nontrivial.

Apply Theorem 1 to \(G\).

If Theorem 1(a) holds, then \(G\) is obtained from a nontrivial \(3\)-critical graph of order \(n-2\) by a vertex-blowup. Since \(n\) is even, \(n-2\) is even, contradicting the minimality of \(n\).

If Theorem 1(b) holds, then \(G\) is obtained from two smaller \(3\)-critical graphs \(G_1\) and \(G_2\) by a Hajós-join. A Hajós-join has order \(|V(G_1)|+|V(G_2)|-1\). Since this number is even, exactly one of \(|V(G_1)|\) and \(|V(G_2)|\) is even. That even-order factor is a smaller even-order \(3\)-critical graph, again contradicting the minimality of \(n\).

If Theorem 1(c) holds, then \(G\) is obtained from a nontrivial \(3\)-critical graph \(G_0\) by a Meredith-type extension using a class 1 graph \(H\) with exactly three degree-\(2\) connector vertices and all other vertices of degree \(3\). Since \(\sum_{v\in V(H)} d_H(v)=3|V(H)|-3\) is even, \(|V(H)|\) is odd. Therefore the extension changes the order by \(|V(H)|-1\), which is even. Thus \(G_0\) has even order smaller than \(n\), contradicting the minimality of \(n\).

Theorem 1(d) cannot occur because \(n\) is even.

It remains to consider the case in Theorem 1(e). Then \(G\) is obtained from a snark \(S\) of order \(n\) by deleting some edges. Since the Petersen graph is the only snark of order less than 18 [18], \(S\) must be the Petersen graph. However, the only 3-critical subgraph of the Petersen graph is the graph obtained by deleting one vertex, a contradiction.

All cases lead to contradictions. Therefore no even-order \(3\)-critical graph of order less than \(18\) exists. ◻

Proof. Since \(G\) is \(3\)-critical, we have \(\Delta(G)=3\), \(\delta(G)\ge 2\), and \(G\) has no bridge. By Vizing’s Adjacency Lemma, no two degree-\(2\) vertices of \(G\) are adjacent, and every degree-\(3\) vertex of \(G\) has at most one neighbor of degree \(2\).

We first record that the needed properties are preserved by the smoothing process. Let \(Q\) be a current graph in the process, and suppose that a degree-\(2\) vertex \(v\) is smoothed. Let the neighbors of \(v\) be \(x\) and \(y\). Since no two degree-\(2\) vertices of \(Q\) are adjacent, both \(x\) and \(y\) have degree \(3\).

Also, by Lemma 5(2), for any cyclic 3-edge-cut \(F\) in \(Q\), \(Q-F\) has exactly two components and \(F\) is a matching in \(Q\).

The smoothing does not create parallel edges. Indeed, suppose that \(xy\in E(Q)\). Since \(v\) is smoothed, one of the edges incident with \(v\), say \(xv\), belongs to a cyclic \(3\)-edge-cut. In the corresponding shore, the vertices \(x\) and \(v\) lie on different sides. If \(y\) lies on the same side as \(v\), then \(xy\) also lies in the cut, and the two cut-edges \(xv\) and \(xy\) have the common end \(x\). If \(y\) lies on the same side as \(x\), then \(vy\) also lies in the cut, and the two cut-edges \(xv\) and \(vy\) have the common end \(v\). Both cases contradict the matching property above. Therefore \(x\) and \(y\) are nonadjacent before the smoothing.

The degree-\(2\) adjacency property is also preserved. Smoothing \(v\) deletes the degree-\(2\) neighbor \(v\) of \(x\) and \(y\) and replaces it by a degree-\(3\) neighbor. Thus no two degree-\(2\) vertices become adjacent, and no degree-\(3\) vertex gains a second degree-\(2\) neighbor.

Bridgelessness is preserved as well. Indeed, if an old edge became a bridge after the smoothing, then it was already a bridge before the smoothing. If the new edge \(xy\) were a bridge after the smoothing, then in the previous graph one of the two edges \(xv\) and \(vy\) would be a bridge, again a contradiction.

Finally, cyclically \(3\)-edge-connectedness is preserved. If smoothing \(v\) created a cyclic edge-cut of size at most \(2\), then replacing the new edge \(xy\) by the path \(xvy\), and placing \(v\) on one of the two sides, would give a cyclic edge-cut of the same size in the previous graph. This contradicts cyclically \(3\)-edge-connectedness of the previous graph.

The process terminates because each smoothing reduces the number of vertices. Thus \(H\) is subcubic, simple, bridgeless, cyclically \(3\)-edge-connected, no two degree-\(2\) vertices of \(H\) are adjacent, every degree-\(3\) vertex of \(H\) has at most one neighbor of degree \(2\), and no degree-\(2\) vertex of \(H\) is an endvertex of an edge belonging to a cyclic \(3\)-edge-cut of \(H\).

Suppose, for a contradiction, that \(H\) has two crossing cyclic \(3\)-edge-cuts. Let these cuts be \(\delta_H(A)\) and \(\delta_H(B)\). Put \[X=A\cap B,\qquad Y=A\setminus B,\qquad Z=B\setminus A,\qquad W=V(H)\setminus(A\cup B).\] See Figure 5 for an illustration of these four sets.

Since \(A\) and \(B\) cross, all four sets \(X,Y,Z,W\) are nonempty. Write \[e_{XY}=e_H(X,Y),\quad e_{XZ}=e_H(X,Z),\quad e_{XW}=e_H(X,W),\] and \[e_{YZ}=e_H(Y,Z),\quad e_{YW}=e_H(Y,W),\quad e_{ZW}=e_H(Z,W).\]

Since \(\delta_H(A)\) and \(\delta_H(B)\) both have size \(3\), we have \[\label{eq:Gstar-cutAB} e_{XZ}+e_{XW}+e_{YZ}+e_{YW}=3 \qquad\text{and}\qquad e_{XY}+e_{XW}+e_{YZ}+e_{ZW}=3.\tag{1}\] The boundary sizes of the four corners are \[|\delta_H(X)|=e_{XY}+e_{XZ}+e_{XW},\] \[|\delta_H(Y)|=e_{XY}+e_{YZ}+e_{YW},\] \[|\delta_H(Z)|=e_{XZ}+e_{YZ}+e_{ZW},\] and \[|\delta_H(W)|=e_{XW}+e_{YW}+e_{ZW}.\] Adding these four equalities gives \[|\delta_H(X)|+|\delta_H(Y)|+|\delta_H(Z)|+|\delta_H(W)| = 2(e_{XY}+e_{XZ}+e_{XW}+e_{YZ}+e_{YW}+e_{ZW}).\] On the other hand, from 1 , \[e_{XY}+e_{XZ}+e_{YW}+e_{ZW}+2e_{XW}+2e_{YZ}=6.\] Thus \[\label{eq:Gstar-corner-sum} |\delta_H(X)|+|\delta_H(Y)|+|\delta_H(Z)|+|\delta_H(W)| = 12-2e_{XW}-2e_{YZ}\le 12.\tag{2}\]

We claim that some corner has boundary size at most \(2\). Indeed, if all four corners had boundary size at least \(3\), then by 2 all four boundary sizes would be exactly \(3\), and also \[e_{XW}=e_{YZ}=0.\] Then 1 gives \[e_{XZ}+e_{YW}=3 \qquad\text{and}\qquad e_{XY}+e_{ZW}=3.\] The four corner-boundary equalities become \[e_{XY}+e_{XZ}=3,\qquad e_{XY}+e_{YW}=3,\] and \[e_{XZ}+e_{ZW}=3,\qquad e_{YW}+e_{ZW}=3.\] From the first two equations, we get \(e_{XZ}=e_{YW}\), which contradicts \(e_{XZ}+e_{YW}=3\). Hence some corner has boundary size at most \(2\).

By replacing \(A\) or \(B\) by its complement, and by interchanging \(A\) and \(B\) if necessary, we may assume that this corner is \(Z\). Indeed, if the small corner is \(X\), replace \(A\) by \(V(H)\setminus A\); if it is \(Y\), interchange \(A\) and \(B\); and if it is \(W\), replace \(B\) by \(V(H)\setminus B\). Since \(\delta_H(A)\) and \(\delta_H(B)\) are cyclic cuts, their complementary shores are also cyclic shores, and crossing is preserved. Therefore we may assume that \(|\delta_H(Z)|\le 2\).

Since \(H\) is connected and bridgeless, and since \(Z\) is nonempty and proper, we have \(|\delta_H(Z)|=2\). If \(H[Z]\) contained a cycle, then \(\delta_H(Z)\) would be a cyclic \(2\)-edge-cut, contradicting cyclically \(3\)-edge-connectedness. Hence \(H[Z]\) is acyclic.

Also \(H[Z]\) is connected. Otherwise one component of \(H[Z]\) would have boundary size at most \(1\), contradicting that \(H\) is connected and bridgeless. Hence \(H[Z]\) is a tree. Since \(|\delta_H(Z)|=2\), we have \[\sum_{v\in Z}d_H(v) = 2e_H(Z)+|\delta_H(Z)| = 2(|Z|-1)+2 = 2|Z|.\] As \(H\) is bridgeless, every vertex of \(H\) has degree at least \(2\). Hence every vertex of \(Z\) has degree exactly \(2\) in \(H\).

If \(|Z|\ge 2\), then the tree \(H[Z]\) contains an edge whose two ends both have degree \(2\) in \(H\), contradicting that no two degree-\(2\) vertices of \(H\) are adjacent. Therefore \(Z\) consists of a single vertex, say \(Z=\{z\}\), and \(d_H(z)=2\).

Now the two edges incident with \(z\) lie in the boundaries of the crossing cyclic \(3\)-cuts \(\delta_H(A)\) and \(\delta_H(B)\). Indeed, an edge from \(z\) to \(X\) lies in \(\delta_H(A)\), an edge from \(z\) to \(W\) lies in \(\delta_H(B)\), and an edge from \(z\) to \(Y\) lies in both \(\delta_H(A)\) and \(\delta_H(B)\). Thus \(z\) is a degree-\(2\) endvertex of an edge belonging to a cyclic \(3\)-edge-cut of \(H\). This contradicts the choice of the final graph \(H\), in which no such degree-\(2\) vertex remains.

Therefore no two cyclic \(3\)-edge-cuts of \(H\) cross. Hence the cyclic \(3\)-edge-cuts of \(H\) are laminar. ◻

Proof of Lemma 12. Since \(G\) is \(3\)-critical, we have \(\Delta(G)=3\), \(\delta(G)\ge 2\), and \(G\) is class \(2\). By Vizing’s Adjacency Lemma, no two degree-\(2\) vertices of \(G\) are adjacent. Moreover, if a degree-\(3\) vertex \(u\) is adjacent to a degree-\(2\) vertex, then the other two neighbors of \(u\) have degree \(3\). Therefore no two degree-\(2\) vertices of \(G\) have a common neighbor.

Let \(G^s\) be the graph obtained from \(G\) by the smoothing process in Lemma 13. Thus \(G^s\) is simple, its cyclic \(3\)-edge-cuts are laminar, and no degree-\(2\) vertex of \(G^s\) is an endvertex of an edge belonging to a cyclic \(3\)-edge-cut. Let \(Z\) be the set of degree-\(2\) vertices of \(G^s\), and let \(R\) be the set of degree-\(2\) vertices of \(G\) which are smoothed out in the process. Hence the degree-\(2\) vertices of \(G\) are exactly the vertices in \(Z\cup R\).

We shall use the following consequence of Lemma 13: if \(G^s\) has a cyclic \(3\)-edge-cut, then both sides of every cyclic \(3\)-edge-cut of \(G^s\) contain a vertex of \(Z\). Indeed, if one side of such a cut contained no vertex of \(Z\), then lifting the cut back to \(G\) and putting all smoothed boundary vertices on the other side would give a cyclic \(3\)-edge-cut of \(G\) whose one side contains no degree-\(2\) vertex, contradicting the hypothesis.

We first dispose of the case where \(G\) has no cyclic \(3\)-edge-cut. In this case no crossing condition is needed. If the number of degree-\(2\) vertices of \(G\) is even, pair them arbitrarily and add one edge for each pair. If the number of degree-\(2\) vertices of \(G\) is odd, choose any three degree-\(2\) vertices, add a new vertex adjacent to them, and pair the remaining degree-\(2\) vertices arbitrarily. Let \(\widehat G\) be the resulting graph. Then \(\widehat G\) is cubic. The arguments below show that \(\widehat G\) is simple, has girth at least \(4\), and is class \(2\). Moreover, the final cyclic-connectivity argument below would imply that any cyclic edge-cut of \(\widehat G\) of size at most \(3\) gives a cyclic \(3\)-edge-cut of \(G\), a contradiction. Hence in this case \(\widehat G\) is cyclically \(4\)-edge-connected.

Thus we may assume from now on that \(G\) has a cyclic \(3\)-edge-cut. Then \(G^s\) also has a cyclic \(3\)-edge-cut, and so \(Z\ne\emptyset\).

The cut tree. We now choose the marks to which the tree pairing will be applied. If \(|R|\) is even, put \[X=Z \qquad\text{and}\qquad R_0=R.\] If \(|R|\) is odd, choose one vertex \(w\in R\), and put \[X=Z\cup\{w\} \qquad\text{and}\qquad R_0=R\setminus\{w\}.\] In both cases, \(R_0\) has even size. The vertices in \(R_0\) will not be used in the cut tree; they will be paired arbitrarily at the end.

We construct a marked tree \(T\) for the active mark set \(X\). First suppose \(|R|\) is even. Since the cyclic \(3\)-edge-cuts of \(G^s\) are laminar, fix one vertex \(z_0\in Z\), and for each cyclic \(3\)-edge-cut of \(G^s\) choose the shore not containing \(z_0\). These chosen shores form a laminar family \(\mathcal{L}\). Adjoin \(V(G^s)\) as a root and order \(\mathcal{L}\cup\{V(G^s)\}\) by inclusion. For \(A,B\in\mathcal{L}\cup\{V(G^s)\}\), call \(B\) a child of \(A\) if \(B\subsetneq A\) and no member of \(\mathcal{L}\cup\{V(G^s)\}\) lies strictly between \(B\) and \(A\). This gives a rooted tree \(T\) whose edges correspond to the cyclic \(3\)-edge-cuts of \(G^s\). Place each vertex of \(Z\) at the smallest member of \(\mathcal{L}\cup\{V(G^s)\}\) containing it. Since both sides of every cyclic \(3\)-edge-cut of \(G^s\) contain a vertex of \(Z\), every edge of \(T\) separates marks from \(X=Z\).

Now suppose \(|R|\) is odd. Let \(w\in R\) be the chosen smoothed-out degree-\(2\) vertex, and let \(a\) and \(b\) be the two neighbors of \(w\) in the original graph \(G\). Thus, in \(G^s\), the path \(awb\) has been smoothed to a single edge \(ab\).

We use the same laminar cut tree for the cyclic \(3\)-edge-cuts of \(G^s\), but we place the additional mark \(w\) at the edge-position corresponding to the smoothed edge \(ab\). Equivalently, in the tree representation, we subdivide this position once and put the mark \(w\) at the new subdivision vertex. This is a single refinement, not a separate subdivision for each cut containing \(ab\).

Let \(Q=\delta_{G^s}(A)\) be a cyclic \(3\)-edge-cut of \(G^s\). If \(ab\notin Q\), then \(a\) and \(b\) lie on the same side of \(Q\), and the mark \(w\) is placed on that same side. If \(ab\in Q\), then exactly one of \(a,b\) lies in \(A\). Say, after relabeling, that \(a\in A\) and \(b\notin A\). After opening \(ab\) back to the path \(awb\), the cut \(Q\) has two possible lifted shores: one uses the edge \(aw\), and the other uses the edge \(wb\). These two lifted shores are nested, corresponding to placing \(w\) on one side of the cut or on the other. Thus every cyclic \(3\)-edge-cut of \(G^s\) using the smoothed edge \(ab\) is recorded by the same edge-position \(ab\), with \(w\) inserted at that position.

It remains to check that every edge of the refined tree separates the active mark set \(X=Z\cup\{w\}\). For tree edges not affected by the insertion of \(w\), this was already true because both sides of the corresponding cyclic \(3\)-edge-cut of \(G^s\) contain vertices of \(Z\). For the two new tree edges created at the position of \(ab\), the two open sides of the corresponding topological cut in \(G^s\) already contain vertices of \(Z\). Hence one new tree edge separates a side containing a vertex of \(Z\) from a side containing \(w\) and another vertex of \(Z\), while the other new tree edge separates a side containing \(w\) and a vertex of \(Z\) from a side containing another vertex of \(Z\). Therefore both new tree edges also separate marks of \(X\).

Thus, also in the case where \(|R|\) is odd, we obtain a finite marked tree \(T\) such that every edge of \(T\) separates marks from \(X=Z\cup\{w\}\).

A pairing fact for marked trees. We use the following elementary fact. Let \(T\) be a finite tree whose marks are vertices, possibly with several marks at the same vertex. Suppose that every edge of \(T\) separates marks. If the number of marks is even, then the marks can be paired so that every edge of \(T\) separates at least one pair. If the number of marks is odd, then three marks can be chosen and the remaining marks can be paired so that every edge of \(T\) either separates one of the pairs or separates the three chosen marks nontrivially, that is, each component of \(T-e\) contains at least one of the three chosen marks.

We prove the fact by induction on the number of vertices of \(T\). First we reduce to the case where every mark lies at a leaf and every leaf contains exactly one mark. Indeed, attach a new leaf for each mark and move the mark to that new leaf. If the desired pairing, or the desired choice of three marks together with a pairing of the remaining marks, works in the enlarged tree, then it also works for the original tree after deleting the added leaf edges. Thus we may assume that every mark is a leaf-mark. In particular, every leaf of \(T\) contains a mark, since an unmarked leaf would give an incident edge whose leaf side contains no mark.

If \(T\) has at most three marks, the result is immediate. If there are two marks, pair them. If there are three marks, choose all three as the special marks. Thus assume that \(T\) has at least four marks in the even case and at least five marks in the odd case.

Let \(z\) be a leaf of \(T\), and let \(m_z\) be the mark at \(z\). Delete \(z\), and then repeatedly delete any unmarked leaf that is created. Let \(T'\) be the resulting tree. Then \(T'\) contains all marks except \(m_z\), and every leaf of \(T'\) contains a mark. Hence every edge of \(T'\) separates the remaining marks: each component of \(T'-e\) contains a leaf of \(T'\), and each leaf of \(T'\) contains a mark. Therefore the induction hypothesis applies to \(T'\). Let \(r\) be the unique vertex of \(T'\) at which the deleted path from \(z\) meets \(T'\).

First suppose that the number of marks of \(T\) is odd. Then the number of marks of \(T'\) is even. By induction, the marks of \(T'\) can be paired so that every edge of \(T'\) separates at least one pair. Choose one pair \(\{a,b\}\) from this pairing. In \(T\), choose the three special marks \(m_z,a,b\), and keep all pairs of the inductive pairing except \(\{a,b\}\).

Every edge on the deleted path from \(z\) to \(r\) separates \(m_z\) from \(a,b\), and hence separates the three special marks nontrivially. Now let \(e\in E(T')\). If \(e\) is separated by one of the kept pairs, then it is covered. Otherwise, in the inductive pairing, the edge \(e\) was separated by the removed pair \(\{a,b\}\). Hence \(a\) and \(b\) lie in different components of \(T'-e\), and so the three special marks \(m_z,a,b\) are separated nontrivially by \(e\). This proves the odd case.

Now suppose that the number of marks of \(T\) is even. Then the number of marks of \(T'\) is odd. By induction, there are three special marks \(a,b,c\) in \(T'\), and the remaining marks of \(T'\) can be paired so that every edge of \(T'\) is either separated by one of the pairs or separates \(a,b,c\) nontrivially.

Let \(R'\) be the minimal subtree of \(T'\) containing \(a,b,c\). Choose a vertex \(u\in V(R')\) as follows. If one of \(a,b,c\) lies on the path between the other two, then let \(u\) be that mark. Otherwise, let \(u\) be the unique vertex of degree \(3\) in \(R'\). Thus \(R'\) is the union of the three paths from \(u\) to \(a,b,c\), where one of these paths may be trivial.

Relabel \(a,b,c\) so that \(a\ne u\) and the component of \(T'-u\) containing \(a\) does not contain \(r\). This is possible as follows. If \(u\) is not one of the three marks \(a,b,c\), then the three paths from \(u\) to \(a,b,c\) start in three distinct components of \(T'-u\), and at most one of these components contains \(r\). Hence one may choose \(a\) from a component not containing \(r\). If \(u\) is one of the three marks, then the other two marks lie in two distinct components of \(T'-u\); again at most one of these components contains \(r\), so one of the other two marks can be chosen as \(a\).

Pair \(m_z\) with \(a\), pair \(b\) with \(c\), and keep all pairs given by the induction on \(T'\). Every edge on the deleted path from \(z\) to \(r\) is separated by the pair \(\{m_z,a\}\). Now let \(e\in E(T')\). If \(e\) is separated by one of the inductive pairs, then it is covered. Otherwise, by the induction hypothesis, \(e\) separates the three marks \(a,b,c\) nontrivially. Hence \(e\) lies in \(R'\), and more precisely \(e\) lies on exactly one of the paths from \(u\) to \(a\), from \(u\) to \(b\), or from \(u\) to \(c\).

If \(e\) lies on the path from \(u\) to \(b\), or on the path from \(u\) to \(c\), then the pair \(\{b,c\}\) separates \(e\). It remains to consider the case where \(e\) lies on the path from \(u\) to \(a\). Let \(A_e\) and \(B_e\) be the two components of \(T'-e\), with \(a\in A_e\) and \(u,b,c\in B_e\). Since \(e\) lies on the path from \(u\) to \(a\), the component \(A_e\) is contained in the component of \(T'-u\) containing \(a\). By the choice of \(a\), this component does not contain \(r\). Hence \(r\in B_e\).

In the original tree \(T\), the deleted path from \(z\) to \(r\) meets \(T'\) only at \(r\). Therefore, after deleting \(e\) from \(T\), the mark \(m_z\) lies in the component containing \(r\), and hence in the component containing \(u,b,c\). Thus \(m_z\) and \(a\) lie in different components of \(T-e\), so the pair \(\{m_z,a\}\) separates \(e\). This proves the even case, and hence the pairing fact.

Choosing the completion. Apply the pairing fact to the marked tree \(T\) with mark set \(X\). Since \(|R_0|\) is even, pair the vertices of \(R_0\) arbitrarily.

If \(|X|\) is even, pair the marks of \(X\) as given by the even case of the pairing fact, and add one new edge for each pair, including the arbitrary pairs in \(R_0\).

If \(|X|\) is odd, choose three special marks in \(X\) and pair the remaining marks of \(X\) as given by the odd case of the pairing fact. Add a new vertex \(x\) adjacent to the three special marks, and add one new edge for each pair, including the arbitrary pairs in \(R_0\).

Let \(\widehat G\) be the resulting graph. Every degree-\(2\) vertex of \(G\) receives exactly one new incident edge, and in the odd case the new vertex \(x\) has degree \(3\). Hence \(\widehat G\) is cubic. We call the added edges, and in the odd case the three edges incident with \(x\), the completion edges.

The crossing property. We claim that every cyclic \(3\)-edge-cut of \(G\) is crossed by at least one completion edge.

Let \(C\) be a cyclic \(3\)-edge-cut of \(G\). If \(|R|\) is even, project \(C\) onto the corresponding cyclic \(3\)-edge-cut of \(G^s\) by replacing each edge of \(C\) with its corresponding smoothed edge in \(G^s\). More precisely, if \(uv\in C\) and \(d_G(u)=d_G(v)=3\), then \(uv\in E(G^s)\). If one of \(u\) and \(v\) has degree 2 in \(G\), say \(d_G(v)=2\), then \(uv\) is replaced by \(uw\in E(G^s)\), where \(w\) is the other neighbor of \(v\) in \(G\). If \(|R|\) is odd, do the same projection for all vertices of \(R_0\), but keep the chosen vertex \(w\) open. Thus in both cases \(C\) determines an edge \(e_T\) of the marked tree \(T\).

If \(|X|\) is even, then by the pairing fact some paired pair of marks in \(X\) is separated by \(e_T\). The corresponding completion edge crosses \(C\).

If \(|X|\) is odd, then either \(e_T\) separates one of the paired pairs, or \(e_T\) separates the three special marks nontrivially. In the first case, the completion edge joining that pair crosses \(C\). In the second case, no matter which side of the cut contains the new vertex \(x\), at least one of the three edges from \(x\) to the special marks crosses \(C\).

This proves the crossing property.

\(\widehat G\) is simple and has girth at least \(4\). By Vizing’s Adjacency Lemma applied to the \(3\)-critical graph \(G\), no two degree-\(2\) vertices of \(G\) are adjacent or share a common neighbor. Each degree-\(2\) vertex is used exactly once in the completion. Therefore no completion edge duplicates an edge of \(G\), and no completion edge creates a triangle. In the case where the new vertex \(x\) is added, its three neighbors are degree-\(2\) vertices of \(G\), and these are pairwise nonadjacent. Thus no triangle passes through \(x\). Since \(G\) has girth at least \(4\), it follows that \(\widehat G\) has girth at least \(4\).

\(\widehat G\) is class \(2\). This follows since \(G\subseteq \widehat G\) and \(G\) is class \(2\).

\(\widehat G\) is cyclically \(4\)-edge-connected. We first record an auxiliary fact. Let \(D\) be one side of an edge-cut of \(G\) of size at most \(3\), and suppose that \(G[D]\) is acyclic. If \(G[D]\) has \(q\) components, then \[\sum_{v\in D}(d_G(v)-2)=|\delta_G(D)|-2q.\] Since \(\delta(G)\ge 2\) and \(|\delta_G(D)|\le 3\), this forces \(q=1\). Thus \(G[D]\) is a tree and the left-hand side is at most \(1\). Hence \(D\) contains at most one vertex of degree \(3\) in \(G\), and all other vertices of \(D\) have degree \(2\) in \(G\). If \(D\) contained two degree-\(2\) vertices of \(G\), then, in this tree, there would either be two adjacent degree-\(2\) vertices or two degree-\(2\) vertices with a common neighbor, contradicting Vizing’s Adjacency Lemma. Hence \[\label{eq:acyclic-side} \text{an acyclic side of an edge-cut of G of size at most 3 contains at most one degree-2 vertex of G.}\tag{3}\]

Suppose, for a contradiction, that \(\widehat G\) has a cyclic edge-cut \(F=\delta_{\widehat G}(A)\) with \(|F|\le 3\). Put \[A_0=A\cap V(G) \qquad\text{and}\qquad C_0=\delta_G(A_0).\] Then \(C_0\subseteq F\), because every edge of \(G\) crossing between \(A_0\) and \(V(G)\setminus A_0\) also crosses between \(A\) and \(V(\widehat G)\setminus A\). Hence \(|C_0|\le 3\).

We claim that both \(G[A_0]\) and \(G[V(G)\setminus A_0]\) contain a cycle. Suppose first that \(G[A_0]\) is acyclic. By 3 , \(A_0\) contains at most one degree-\(2\) vertex of \(G\). Since \(F\) is cyclic, the \(A\)-side of \(\widehat G-F\) contains a cycle. This cycle cannot lie entirely in \(G[A_0]\), so it uses a completion edge. A paired completion edge with exactly one end in \(A_0\) lies in \(F\) and is absent from the \(A\)-side of \(\widehat G-F\). Hence any paired completion edge used by the cycle has both ends in \(A_0\), giving at least two degree-\(2\) vertices of \(G\) in \(A_0\). In the case where the cycle uses the new vertex \(x\), it uses two edges incident with \(x\), and again their old ends give at least two degree-\(2\) vertices of \(G\) in \(A_0\). Both possibilities contradict 3 . Therefore \(G[A_0]\) contains a cycle. The same argument applied to the other side shows that \(G[V(G)\setminus A_0]\) contains a cycle.

Thus \(C_0\) is a cyclic edge-cut of \(G\) with \(|C_0|\le 3\). Since \(G\) is cyclically \(3\)-edge-connected, we have \(|C_0|=3\). If \(G\) has no cyclic \(3\)-edge-cut, this is already a contradiction. Otherwise, \(C_0\) is a cyclic \(3\)-edge-cut of \(G\), and by the crossing property some completion edge crosses \(C_0\). Therefore this completion edge lies in \(F\).

But \(C_0\subseteq F\) and the three edges of \(C_0\) are edges of \(G\), while the completion edge is not an edge of \(G\). Hence \(|F|\ge |C_0|+1=4\), contradicting \(|F|\le 3\). Therefore \(\widehat G\) has no cyclic edge-cut of size at most \(3\), and so \(\widehat G\) is cyclically \(4\)-edge-connected.

Combining the preceding parts, \(\widehat G\) is a cyclically \(4\)-edge-connected cubic class \(2\) graph of girth at least \(4\). ◻