Introduction
A perfect matching is an edge set in which every vertex is incident with exactly one edge. Perfect matchings have played a central role in graph theory since the late nineteenth century, with applications in combinatorial optimization, coding theory, and network design. In particular, for cubic graphs, perfect matchings provide an important tool for studying structural connectivity and resilience.
A fundamental theorem of Petersen states that every bridgeless cubic graph has a perfect matching [7 ] . Schönberger subsequently proved the corresponding edgewise statement: every edge of a bridgeless cubic graph belongs to at least one perfect matching [9 ] . Thus, for cubic graphs, bridgelessness is equivalent to the property that every edge belongs to some perfect matching. These results established the basic connection between bridges and perfect-matching coverage.
Later research turned from the existence of perfect matchings to their number and distribution. Esperet et al. proved that the number of perfect matchings in a bridgeless cubic graph grows exponentially with the order of the graph [1 ] . This result motivates studying the multiplicity with which individual edges occur in perfect matchings. A cubic graph is called matching double covered if every edge belongs to at least two distinct perfect matchings. Consequently, edges that occur in exactly one perfect matching form a natural exceptional class. Goedgebeur et al. introduced the term lonely edge for an edge that belongs to exactly one perfect matching and initiated a systematic study of non-double-covered cubic graphs [5 ] . Their work builds on an earlier result of Esperet et al., who proved that every 3-connected cubic graph is matching double covered unless it belongs to a special class of graphs called Klee graphs [2 ] .
Klee graphs are defined recursively by starting with K 4 K_4 K 4 and replacing vertices by triangles. Fiorini and Wilson conjectured that Klee graphs are precisely the planar cubic graphs with a unique 3-edge-colouring, and a proof of this conjecture was given in Fowler’s doctoral thesis [3 , 4 ] . Not every Klee graph is non-double covered. For example, the truncation of K 4 K_4 K 4 is still matching double covered. Thus, a more precise structural analysis is needed to identify exactly which Klee graphs contain lonely edges.
Goedgebeur et al. reduced the study of bridgeless non-double-covered cubic graphs to their 3-connected components by means of 2-cut reductions [5 ] . Within the resulting 3-connected setting, they developed a constructive framework based on vertex-to-triangle replacements and spanning subgraph joins. For k ≥ 1 k \ge1 k ≥ 1 , let U k \mathcal{U}_k U k denote the subclass of graphs in this framework having exactly k k k lonely edges. Several cases were settled in their work. They proved that no graph in the considered class has more than six lonely edges and that U k = ∅ \mathcal{U}_k = \varnothing U k = ∅ for k > 6 k > 6 k > 6 . Moreover, they also characterized the classes with three, four, five and six lonely edges [5 ] . In addition, they exhibited infinite families in U 1 \mathcal{U}_1 U 1 and U 2 \mathcal{U}_2 U 2 , showing that the cases with at least three lonely edges and those with one or two lonely edges have substantially different structural behaviour. For example, graphs in U 1 \mathcal{U}_1 U 1 and U 2 \mathcal{U}_2 U 2 can contain arbitrarily many triangles, whereas those in U 3 , U 4 , U 5 , U 6 \mathcal{U}_3,\mathcal{U}_4,\mathcal{U}_5,\mathcal{U}_6 U 3 , U 4 , U 5 , U 6 contain at most three triangles, except for K 4 K_4 K 4 , which contains four triangles. Recently, Narayana et al. gave a recursive characterization of the subclass in which the two lonely edges lie in the same perfect matching.
The present paper focuses on the class U 2 \mathcal{U}_2 U 2 of 3-connected non-double-covered cubic graphs with exactly two lonely edges. The main objective is to give a complete structural characterization of this class. We address the following two questions.
Which graphs in U 2 \mathcal{U}_2 U 2 are minimally non-contractible to a smaller graph in U 2 \mathcal{U}_2 U 2 ? We call such graphs primitive U 2 \mathcal{U}_2 U 2 kernels .
Given an arbitrary graph G ∈ U 2 G \in\mathcal{U}_2 G ∈ U 2 , can G G G be obtained from a primitive kernel by a finite sequence of expansions, while every intermediate graph remains in U 2 \mathcal{U}_2 U 2 ?
The first question is answered in Section 3, where we classify all primitive U 2 \mathcal{U}_2 U 2 kernels. The second question is addressed in Section 4, where we introduce standard markings and prove that the relevant zero-loss expansions preserve membership in U 2 \mathcal{U}_2 U 2 . Together, these results provide a constructive characterization of every graph in U 2 \mathcal{U}_2 U 2 from a primitive kernel.
Preliminaries
Throughout this paper, all graphs are assumed to be finite, simple, and cubic unless explicitly stated otherwise. Our work builds directly upon the framework established in [5 ] ; we therefore adopt most of the notation and conventions introduced therein, with only minor modifications made to simplify subsequent discussions. For the sake of completeness and readability, we restate key definitions below.
Let N G ( v ) = { x , y , z } N_G(v) = \{x,y,z\} N G ( v ) = { x , y , z } . When v v v is replaced by a triangle, label the three new vertices v x v_x v x , v y v_y v y , v z v_z v z , where v x v_x v x is adjacent to the old neighbor x x x , v y v_y v y to y y y , and v z v_z v z to z z z . Add the three triangle edges v x v y v_xv_y v x v y , v y v z v_yv_z v y v z , v z v x v_zv_x v z v x . The opposite edge of the old edge v x vx v x is v y v z v_yv_z v y v z . This labeling depends only on the old neighbors in the current step, so every operation is completely determined at the vertex-label level. A join rooted at v v v is a spanning subgraph J J J of G G G such that d J ( v ) = 3 d_J(v)=3 d J ( v ) = 3 and d J ( u ) = 1 d_J(u)=1 d J ( u ) = 1 for every u ≠ v u\ne v u = v , where d J ( v ) d_J(v) d J ( v ) represents the degree of v v v in J J J . Since G G G is cubic, J J J necessarily contains all three edges incident with v v v .
Definition 2.1. A graph G G G is a Klee-graph if G = K 4 G=K_4 G = K 4 or there exists a Klee-graph H H H and a vertex w ∈ V ( H ) w\in V(H) w ∈ V ( H ) such that G = H w G=H^w G = H w . We denote the set of Klee-graphs by K \mathcal{K} K .
Let G ∈ K G\in\mathcal{K} G ∈ K . Suppose that a graph H H H can be obtained from G G G through a finite sequence of vertex expansion operations, where each operation replaces a single vertex with a triangle. In such cases, we refer to H H H as a descendant of G G G . Building on this parent-descendant framework, we further define a direct hierarchical relationship: for any vertex v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , the graph G v G^v G v obtained by expanding v v v into a triangle is called a child of G G G , and conversely, G G G is called the parent of G v G^v G v . Let M ( G ) \mathcal{M}(G) M ( G ) denote the set of perfect matchings of G G G . An edge e e e is called a lonely edge if it belongs to exactly one member of M ( G ) \mathcal{M}(G) M ( G ) . Put
L ( G ) = { e ∈ E ( G ) : ∣ { M ∈ M ( G ) : e ∈ M } ∣ = 1 } , ℓ ( G ) = ∣ L ( G ) ∣ . L(G)=\{e\in E(G):|\{M\in\mathcal{M}(G):e\in M\}|=1\},\qquad\ell(G)=|L(G)|. L ( G ) = { e ∈ E ( G ) : ∣ { M ∈ M ( G ) : e ∈ M } ∣ = 1 } , ℓ ( G ) = ∣ L ( G ) ∣.
Write
U k = { G ∈ K : ℓ ( G ) = k } , U = ⋃ k ≥ 1 U k . \mathcal{U}_k=\{G\in\mathcal{K}:\ell(G)=k\},\qquad\mathcal{U}=\bigcup_{k\ge1}\mathcal{U}_k. U k = { G ∈ K : ℓ ( G ) = k } , U = k ≥ 1 ⋃ U k .
Definition 2.2. For G ∈ U G\in\mathcal{U} G ∈ U and v ∈ V ( G ) v\in V(G) v ∈ V ( G ) , define
Σ G ( v ) = { e ∈ L ( G ) : v ∉ V ( e ) , and there exists a join rooted at v that contains e } . \Sigma_G(v)=\{e\in L(G):v\notin V(e),\text{ and there exists a join rooted at }v\text{ that contains }e\}. Σ G ( v ) = { e ∈ L ( G ) : v ∈ / V ( e ) , and there exists a join rooted at v that contains e } . We simultaneously define a vertex v v v satisfying Σ G ( v ) = ∅ \Sigma_G(v)=\varnothing Σ G ( v ) = ∅ as a zero-loss expansion vertex , or alternatively refer to such a vertex as zero-loss expandable .
Lemma 2.3. Let x y ∈ L ( G ) xy\in L(G) x y ∈ L ( G ) and v ∉ { x , y } v\notin\{x,y\} v ∈ / { x , y } . Then x y ∈ Σ G ( v ) xy\in\Sigma_G(v) x y ∈ Σ G ( v ) if and only if
{ x , y } ∩ N G [ v ] = ∅ and G − N G [ v ] − { x , y } has a perfect matching . \{x,y\}\cap N_G[v]=\varnothing\quad\text{and}\quad G-N_G[v]-\{x,y\}\text{ has a perfect matching}. { x , y } ∩ N G [ v ] = ∅ and G − N G [ v ] − { x , y } has a perfect matching . Proof. If J J J is a join rooted at v v v containing x y xy x y , then J J J contains all three edges incident with v v v . Hence every vertex in N ( v ) N(v) N ( v ) already has degree 1 1 1 in J J J , so neither x x x nor y y y lies in N [ v ] N[v] N [ v ] . After deleting N [ v ] ∪ { x , y } N[v]\cup\{x,y\} N [ v ] ∪ { x , y } , the remaining edges of J J J are pairwise disjoint and cover all remaining vertices, and therefore form a perfect matching.
Conversely, suppose that { x , y } ∩ N [ v ] = ∅ \{x,y\}\cap N[v]=\varnothing { x , y } ∩ N [ v ] = ∅ and that M M M is a perfect matching of G − N [ v ] − { x , y } G-N[v]-\{x,y\} G − N [ v ] − { x , y } . Then M ∪ { x y } ∪ { v w : w ∈ N ( v ) } M\cup\{xy\}\cup\{vw:w\in N(v)\} M ∪ { x y } ∪ { v w : w ∈ N ( v )} is a join rooted at v v v containing x y xy x y . This proves both directions.
Let N G ( v ) = { x , y , z } N_G(v)=\{x,y,z\} N G ( v ) = { x , y , z } . Define the transfer map on lonely edges by
λ v ( e ) = { e , v ∉ V ( e ) , v a v b , e = v c where { a , b , c } = { x , y , z } . \lambda_v(e)=
\begin{cases}
e, & v\notin V(e),\\
v_av_b, & e=vc\text{ where }\{a,b,c\}=\{x,y,z\}.
\end{cases} λ v ( e ) = { e , v a v b , v ∈ / V ( e ) , e = v c where { a , b , c } = { x , y , z } .
The following result is the set-valued form of [5 Lemma 3.5 and Corollary 3.6] .
Proposition 2.4. Let G ∈ U G\in\mathcal{U} G ∈ U and v ∈ V ( G ) v\in V(G) v ∈ V ( G ) . Then
L ( G v ) = { λ v ( e ) : e ∈ L ( G ) ∖ Σ G ( v ) } . (1) L(G^v)=\{\lambda_v(e):e\in L(G)\setminus\Sigma_G(v)\}. \tag*{(1)} L ( G v ) = { λ v ( e ) : e ∈ L ( G ) ∖ Σ G ( v )} . (1) and
ℓ ( G v ) = ℓ ( G ) − ∣ Σ G ( v ) ∣ . (2) \ell(G^v)=\ell(G)-|\Sigma_G(v)|. \tag*{(2)} ℓ ( G v ) = ℓ ( G ) − ∣ Σ G ( v ) ∣. (2)
Corollary 2.5. If G ∈ U k G \in\mathcal{U}_k G ∈ U k , then G v ∈ U 2 G^v \in\mathcal{U}_2 G v ∈ U 2 if and only if ∣ Σ G ( v ) ∣ = k − 2 |\Sigma_G(v)| = k - 2 ∣ Σ G ( v ) ∣ = k − 2 .
Corollary 2.6. Let G ∈ U G \in\mathcal{U} G ∈ U and N G ( v ) = { x , y , z } N_G(v) = \{x,y,z\} N G ( v ) = { x , y , z } . Then { v x x , v y y , v z z } ∩ L ( G v ) = ∅ \{v_{xx},v_{yy},v_{zz}\} \cap L(G^v) = \varnothing { v xx , v y y , v z z } ∩ L ( G v ) = ∅ .
Proof. Let w w w be an arbitrary vertex in { x , y , z } \{x,y,z\} { x , y , z } . If v w ∈ L ( G ) vw \in L(G) v w ∈ L ( G ) , then, by Proposition 2.4 , w v w ∉ L ( G v ) wvw \notin L(G^v) w v w ∈ / L ( G v ) . Otherwise, v w ∉ L ( G ) vw \notin L(G) v w ∈ / L ( G ) . Then v w vw v w is contained in at least two perfect matchings of G G G . Let M v w M_{vw} M v w and M v w ′ M'_{vw} M v w ′ be two distinct perfect matchings of G G G containing v w vw v w . Then M v w − v w + w v w + e M_{vw} - vw + wv_w + e M v w − v w + w v w + e , M v w ′ − v w + w v w + e M'_{vw} - vw + wv_w + e M v w ′ − v w + w v w + e are two distinct perfect matchings of G v G^v G v , where e e e denotes the edge opposite v w vw v w . Hence, w v w ∉ L ( G v ) wv_w \notin L(G^v) w v w ∈ / L ( G v ) . Combining the above, we obtain { v x x , v y y , v z z } ∩ L ( G v ) = ∅ \{v_{xx},v_{yy},v_{zz}\} \cap L(G^v) = \varnothing { v xx , v y y , v z z } ∩ L ( G v ) = ∅ .
Definition 2.7. A graph C ∈ U 2 C \in\mathcal{U}_2 C ∈ U 2 is called a primitive U 2 \mathcal{U}_2 U 2 kernel if, for every triangle T T T of C C C , C / T ∉ U 2 C/T \notin\mathcal{U}_2 C / T ∈ / U 2 , where C / T C/T C / T is the cubic graph obtained by contracting T T T to a single vertex.
Definition 2.8. For a graph family A ⊆ U 2 \mathcal{A} \subseteq\mathcal{U}_2 A ⊆ U 2 , let Neu ( A ) \operatorname{Neu}(\mathcal{A}) Neu ( A ) be the smallest family satisfying:
(a) A ⊆ Neu ( A ) \mathcal{A} \subseteq\operatorname{Neu}(\mathcal{A}) A ⊆ Neu ( A ) ;
(b) if G ∈ Neu ( A ) G \in\operatorname{Neu}(\mathcal{A}) G ∈ Neu ( A ) and Σ G ( v ) = ∅ \Sigma_G(v) = \varnothing Σ G ( v ) = ∅ , then G v ∈ Neu ( A ) G^v \in\operatorname{Neu}(\mathcal{A}) G v ∈ Neu ( A ) .
Proposition 2.9. Let C \mathcal{C} C be the set of all primitive U 2 \mathcal{U}_2 U 2 kernels. Then U 2 = Neu ( C ) \mathcal{U}_2 = \operatorname{Neu}(\mathcal{C}) U 2 = Neu ( C ) .
Proof. By Proposition 2.4 , expanding a graph in U 2 \mathcal{U}_2 U 2 at a vertex satisfying Σ G ( v ) = ∅ \Sigma_G(v) = \varnothing Σ G ( v ) = ∅ keeps the graph in U 2 \mathcal{U}_2 U 2 , so Neu ( C ) ⊆ U 2 \operatorname{Neu}(\mathcal{C}) \subseteq\mathcal{U}_2 Neu ( C ) ⊆ U 2 . Conversely, take any G ∈ U 2 G \in\mathcal{U}_2 G ∈ U 2 . If G G G is not primitive, there is a triangle T T T such that G / T ∈ U 2 G/T \in\mathcal{U}_2 G / T ∈ U 2 . Repeating such contractions decreases the order by 2 2 2 at every step, so the process terminates after finitely many steps at some primitive kernel C C C . Reversing the contraction sequence gives C = G 0 , G 1 , ⋯ , G s = G C = G_0, G_1, \cdots, G_s = G C = G 0 , G 1 , ⋯ , G s = G with G i + 1 = G i v i G_{i+1} = G_i^{v_i} G i + 1 = G i v i and every G i , G i + 1 ∈ U 2 G_i, G_{i+1} \in\mathcal{U}_2 G i , G i + 1 ∈ U 2 . By Proposition 2.4 , 2 = ℓ ( G i + 1 ) = ℓ ( G i ) − ∣ Σ G i ( v i ) ∣ = 2 − ∣ Σ G i ( v i ) ∣ 2 = \ell(G_{i+1}) = \ell(G_i) - |\Sigma_{G_i}(v_i)| = 2 - |\Sigma_{G_i}(v_i)| 2 = ℓ ( G i + 1 ) = ℓ ( G i ) − ∣ Σ G i ( v i ) ∣ = 2 − ∣ Σ G i ( v i ) ∣ . It follows that Σ G i ( v i ) = ∅ \Sigma_{G_i}(v_i) = \varnothing Σ G i ( v i ) = ∅ . Thus, G ∈ Neu ( C ) G \in\operatorname{Neu}(\mathcal{C}) G ∈ Neu ( C ) .
Proposition 2.9 shows that the only substantive task remaining is to classify the primitive kernels.
The primitive kernels of U 2 \mathcal{U}_2 U 2
The triangular prism is composed of two vertex-disjoint triangles, denoted U = u 1 u 2 u 3 U = u_1u_2u_3 U = u 1 u 2 u 3 and X 0 = x 1 0 x 2 0 x 3 0 X^0 = x_1^0x_2^0x_3^0 X 0 = x 1 0 x 2 0 x 3 0 , which are connected by the matching edges { u i x i 0 ∣ i = 1 , 2 , 3 } \{u_ix_i^0 \mid i = 1,2,3\} { u i x i 0 ∣ i = 1 , 2 , 3 } . To formalize the iterative expansion process, the concept of an “active-end triangle” is defined: at each step t ≥ 1 t \ge1 t ≥ 1 , let X t − 1 = x 1 t − 1 x 2 t − 1 x 3 t − 1 X^{t-1} = x_1^{t-1}x_2^{t-1}x_3^{t-1} X t − 1 = x 1 t − 1 x 2 t − 1 x 3 t − 1 denote the triangle targeted for modification. An expansion with index s t ∈ { 1 , 2 , 3 } s_t \in\{1,2,3\} s t ∈ { 1 , 2 , 3 } is performed by replacing the vertex x s t t − 1 x_{s_t}^{t-1} x s t t − 1 with a new triangle X t = x 1 t x 2 t x 3 t X^t = x_1^tx_2^tx_3^t X t = x 1 t x 2 t x 3 t , where for each j ≠ s t j \ne s_t j = s t , the new vertex x j t x_j^t x j t is adjacent to the original vertex x j t − 1 x_j^{t-1} x j t − 1 . By applying a sequence of such expansions following a pattern w = s 1 s 2 ⋯ s m w = s_1s_2 \cdots s_m w = s 1 s 2 ⋯ s m , a graph known as an extended prism is constructed, which is denoted by P ( w ) P(w) P ( w ) .
It is readily observed that P ( s 1 s 2 ⋯ s m ) P(s_1s_2 \cdots s_m) P ( s 1 s 2 ⋯ s m ) is constructed by inserting a total of 2 m 2m 2 m new vertices into the edges in { u i x i 0 ∣ 1 ≤ i ≤ 3 } \{u_ix_i^0 \mid1 \le i \le3\} { u i x i 0 ∣ 1 ≤ i ≤ 3 } , with the restriction that each edge is subdivided at most m m m times, and relabeling x i 0 x_i^0 x i 0 as x i m x_i^m x i m . The path P i P_i P i with endpoints u i u_i u i and x i m x_i^m x i m obtained through this subdivision is hereafter referred to as the i i i -rail. Additionally, m m m edges are added to connect these vertices (specifically, at step t t t , one vertex is inserted on each i i i -rail with i ∈ { 1 , 2 , 3 } ∖ { s t } i \in\{1,2,3\} \setminus\{s_t\} i ∈ { 1 , 2 , 3 } ∖ { s t } , and an edge is then added between these two vertices); the edge is called a k k k -rung if both its endpoints have the superscript k k k (0 ≤ k ≤ m − 1 0 \le k \le m-1 0 ≤ k ≤ m − 1 ) and distinct subscripts. An example of P ( 312231 ) P(312231) P ( 312231 ) is shown in Figure 1 . By flipping this graph upside down, it can be observed that P ( s 1 s 2 ⋯ s m − 1 s m ) P(s_1s_2 \cdots s_{m-1}s_m) P ( s 1 s 2 ⋯ s m − 1 s m ) is isomorphic to P ( s m s m − 1 ⋯ s 2 s 1 ) P(s_ms_{m-1} \cdots s_2s_1) P ( s m s m − 1 ⋯ s 2 s 1 ) .
Figure 1. The extended prism P ( 312231 ) P(312231) P ( 312231 )
Part (1) of the following lemma is implicit in the definition of extended prisms and in the proof of Theorem 3.12 in Godegebuer et al. [5 ] , while part (2) is directly derived from the construction of extended prisms.
Lemma 3.1. (1) A Klee graph of order at least 6 has exactly two triangles if and only if it is an extended prism.
(2) For m ≥ 1 m \ge1 m ≥ 1 , the two triangles of P ( s 1 ⋯ s m ) P(s_1 \cdots s_m) P ( s 1 ⋯ s m ) are precisely the fixed left end and the active right end; contracting the right end yields P ( s 1 ⋯ s m − 1 ) P(s_1 \cdots s_{m-1}) P ( s 1 ⋯ s m − 1 ) , while contracting the left end yields a graph isomorphic to P ( s m ⋯ s 2 ) P(s_m \cdots s_2) P ( s m ⋯ s 2 ) .
Armed with these definitions, we proceed to present the characterizations of U i \mathcal{U}_i U i for 3 ≤ i ≤ 6 3 \le i \le6 3 ≤ i ≤ 6 established by Goedgebeur et al. [5 ] .
Theorem 3.2. [5 ] A graph G G G belongs to U 3 \mathcal{U}_3 U 3 if and only if
G ∈ W 3 ∪ { P ( 1 h − 1 3 2 p − h ) : p , h ∈ Z , p ≥ 3 , p + 1 2 ≤ h ≤ p } , G \in\mathcal{W}_3 \cup\{P(1^{h-1}3\,2^{p-h}) : p,h \in\mathbb{Z},\ p \ge3,\ \frac{p+1}{2} \le h \le p\}, G ∈ W 3 ∪ { P ( 1 h − 1 3 2 p − h ) : p , h ∈ Z , p ≥ 3 , 2 p + 1 ≤ h ≤ p } , where W 3 = { T 0 , T 1 , T 2 , T 3 , P ( 121 ) } \mathcal{W}_3 = \{T_0,T_1,T_2,T_3,P(121)\} W 3 = { T 0 , T 1 , T 2 , T 3 , P ( 121 )} and T 0 , T 1 , T 2 , T 3 T_0,T_1,T_2,T_3 T 0 , T 1 , T 2 , T 3 are shown in Figure 3 .
Figure 3. The finite tricorn branch. In all four graphs the lonely edges are (1, 3), (4, 8), (6, 7).
Theorem 3.3. [5 ] A graph G G G belongs to U 4 \mathcal{U}_4 U 4 if and only if G ∈ { P ( 12 ) } ∪ { P ( 1 p ) : p ≥ 2 } G \in\{P(12)\} \cup\{P(1^p) : p \ge2\} G ∈ { P ( 12 )} ∪ { P ( 1 p ) : p ≥ 2 } .
Theorem 3.4. [5 ] The following statements hold.
(i) ℓ ( G ) ≤ 6 \ell(G) \le6 ℓ ( G ) ≤ 6 for every G ∈ U G \in\mathcal{U} G ∈ U ;
(ii) The bicorn is the only element of U 5 \mathcal{U}_5 U 5 (see Figure 2 );
(iii) K 4 K_4 K 4 and the triangular prism P r \mathop{\mathrm{Pr}} Pr are the only elements of U 6 \mathcal{U}_6 U 6 .
Figure 2. All graphs of U 5 \mathcal{U}_5 U 5 and U 6 \mathcal{U}_6 U 6
The structural properties of extended prisms
For a thorough characterization of U 2 \mathcal{U}_2 U 2 , it is necessary to further investigate the structural properties of extended prisms. We now state several fundamental properties of such graphs.
Let w = s 1 s 2 ⋯ s m w = s_1s_2 \cdots s_m w = s 1 s 2 ⋯ s m and w ′ w' w ′ be words of the same length, and let rev ( w ) = s m s m − 1 ⋯ s 1 \operatorname{rev}(w) = s_ms_{m-1} \cdots s_1 rev ( w ) = s m s m − 1 ⋯ s 1 . We write w ∼ w ′ w \sim w' w ∼ w ′ if there exists a permutation π ∈ S 3 \pi\in S_3 π ∈ S 3 such that either w ′ = π ( w ) w' = \pi(w) w ′ = π ( w ) or w ′ = π ( rev ( w ) ) w' = \pi(\operatorname{rev}(w)) w ′ = π ( rev ( w )) , where π ( w ) = π ( s 1 ) π ( s 2 ) ⋯ π ( s m ) \pi(w) = \pi(s_1)\pi(s_2) \cdots\pi(s_m) π ( w ) = π ( s 1 ) π ( s 2 ) ⋯ π ( s m ) . Since reversal commutes with symbol permutations and applying reversal twice gives the original word, it is easy to verify that this relation is transitive.
Lemma 3.5. P ( w ) ≅ P ( w ′ ) P(w) \cong P(w') P ( w ) ≅ P ( w ′ ) if and only if w ∼ w ′ w \sim w' w ∼ w ′ .
Proof. For convenience, we denote the vertices in P ( w ) P(w) P ( w ) by u i u_i u i , x i j x_i^j x i j and the vertices in P ( w ′ ) P(w') P ( w ′ ) by u i ′ u_i' u i ′ , x i ′ j x_i^{\prime j} x i ′ j (if they exist), where i ∈ { 1 , 2 , 3 } i \in\{1,2,3\} i ∈ { 1 , 2 , 3 } and j ∈ { 0 , 1 , … , m } j \in\{0,1,\ldots,m\} j ∈ { 0 , 1 , … , m } . Let w = s 1 s 2 ⋯ s m w=s_1s_2\cdots s_m w = s 1 s 2 ⋯ s m and w ′ = s 1 ′ s 2 ′ ⋯ s m ′ w'=s_1's_2'\cdots s_m' w ′ = s 1 ′ s 2 ′ ⋯ s m ′ . We prove the two directions separately.
Sufficiency. Suppose that w ∼ w ′ w \sim w' w ∼ w ′ . Then there exists π ∈ S 3 \pi\in S_3 π ∈ S 3 such that w ′ = π ( w ) w'=\pi(w) w ′ = π ( w ) or w ′ = π ( rev ( w ) ) w'=\pi(\operatorname{rev}(w)) w ′ = π ( rev ( w )) . For w ′ = π ( w ) w'=\pi(w) w ′ = π ( w ) , we construct an isomorphism between P ( w ) P(w) P ( w ) and P ( w ′ ) P(w') P ( w ′ ) as follows:
u i ⟼ u π ( i ) ′ , x i t ⟼ x π ( i ) ′ t , u_i \longmapsto u'_{\pi(i)}, \qquad x_i^t \longmapsto x_{\pi(i)}^{\prime t}, u i ⟼ u π ( i ) ′ , x i t ⟼ x π ( i ) ′ t ,
where 0 ≤ t ≤ m 0 \le t \le m 0 ≤ t ≤ m , and the map is defined only for vertices that exist. By the construction of extended prisms, this bijection preserves adjacency.
For w ′ = π ( rev ( w ) ) w'=\pi(\operatorname{rev}(w)) w ′ = π ( rev ( w )) , we first show that P ( w ) ≅ P ( rev ( w ) ) P(w) \cong P(\operatorname{rev}(w)) P ( w ) ≅ P ( rev ( w )) . Denote the vertices of P ( rev ( w ) ) P(\operatorname{rev}(w)) P ( rev ( w )) by u ~ i \widetilde{u}_i u i , x ~ i t \widetilde{x}_i^t x i t . Define
u i ⟼ x ~ i m , x i m ⟼ u ~ i , x i t ⟼ x ~ i m − t − 1 , u_i \longmapsto\widetilde{x}_i^m, \qquad x_i^m \longmapsto\widetilde{u}_i, \qquad x_i^t \longmapsto\widetilde{x}_i^{m-t-1}, u i ⟼ x i m , x i m ⟼ u i , x i t ⟼ x i m − t − 1 ,
where 0 ≤ t ≤ m − 1 0 \le t \le m-1 0 ≤ t ≤ m − 1 in the last formula, again considering only existing vertices. Indeed, x i t x_i^t x i t exists precisely when i ≠ s t + 1 i \ne s_{t+1} i = s t + 1 , which is also the condition for x ~ i m − t − 1 \widetilde{x}_i^{m-t-1} x i m − t − 1 to exist. This bijection exchanges the two end triangles, reverses each rail, and maps each rung to the corresponding rung. Hence it is an isomorphism. By the first case, P ( rev ( w ) ) ≅ P ( π ( rev ( w ) ) ) P(\operatorname{rev}(w)) \cong P(\pi(\operatorname{rev}(w))) P ( rev ( w )) ≅ P ( π ( rev ( w ))) . Thus P ( w ) ≅ P ( w ′ ) P(w) \cong P(w') P ( w ) ≅ P ( w ′ ) .
Necessity. Suppose that φ \varphi φ is an isomorphism between P ( w ) P(w) P ( w ) and P ( w ′ ) P(w') P ( w ′ ) . Since every extended prism has exactly two triangles, namely its two end triangles, φ \varphi φ must either preserve these two triangles individually, in which case
φ ( u 1 ) = u i 1 ′ , φ ( u 2 ) = u i 2 ′ , φ ( u 3 ) = u i 3 ′ , \varphi(u_1)=u'_{i_1}, \qquad\varphi(u_2)=u'_{i_2}, \qquad\varphi(u_3)=u'_{i_3}, φ ( u 1 ) = u i 1 ′ , φ ( u 2 ) = u i 2 ′ , φ ( u 3 ) = u i 3 ′ ,
or interchange them, in which case
φ ( u 1 ) = x i 1 ′ m , φ ( u 2 ) = x i 2 ′ m , φ ( u 3 ) = x i 3 ′ m . \varphi(u_1)=x_{i_1}^{\prime m}, \qquad\varphi(u_2)=x_{i_2}^{\prime m}, \qquad\varphi(u_3)=x_{i_3}^{\prime m}. φ ( u 1 ) = x i 1 ′ m , φ ( u 2 ) = x i 2 ′ m , φ ( u 3 ) = x i 3 ′ m .
For the first case, let π = ( 1 2 3 i 1 i 2 i 3 ) \pi=\begin{pmatrix}1&2&3\\i_1&i_2&i_3\end{pmatrix} π = ( 1 i 1 2 i 2 3 i 3 ) . We prove by induction on m m m that w ′ = π ( w ) w'=\pi(w) w ′ = π ( w ) and that φ ( x i m ) = x π ( i ) ′ m \varphi(x_i^m)=x_{\pi(i)}^{\prime m} φ ( x i m ) = x π ( i ) ′ m for every i ∈ { 1 , 2 , 3 } i\in\{1,2,3\} i ∈ { 1 , 2 , 3 } . When m = 0 m=0 m = 0 , both graphs are triangular prisms, and the three edges joining their end triangles force the same permutation on both ends. Suppose that m ≥ 1 m\ge1 m ≥ 1 . Contracting the right end triangle in each graph induces an isomorphism
φ ‾ : P ( s 1 ⋯ s m − 1 ) ⟶ P ( s 1 ′ ⋯ s m − 1 ′ ) . \overline{\varphi}:P(s_1\cdots s_{m-1})\longrightarrow P(s_1'\cdots s_{m-1}'). φ : P ( s 1 ⋯ s m − 1 ) ⟶ P ( s 1 ′ ⋯ s m − 1 ′ ) .
This induced isomorphism preserves the left end and hence also the right end, since each contracted graph has exactly two triangles. By the induction hypothesis,
s t ′ = π ( s t ) ( 1 ≤ t < m ) , φ ‾ ( x i m − 1 ) = x π ( i ) ′ m − 1 ( i ∈ { 1 , 2 , 3 } ) . s_t'=\pi(s_t) \quad(1\le t<m), \qquad\overline{\varphi}(x_i^{m-1})=x_{\pi(i)}^{\prime m-1} \quad(i\in\{1,2,3\}). s t ′ = π ( s t ) ( 1 ≤ t < m ) , φ ( x i m − 1 ) = x π ( i ) ′ m − 1 ( i ∈ { 1 , 2 , 3 }) .
The contracted vertices are x s m m − 1 x_{s_m}^{m-1} x s m m − 1 and x s m ′ ′ m − 1 x_{s_m'}^{\prime m-1} x s m ′ ′ m − 1 , respectively. Therefore, x π ( s m ) ′ m − 1 = φ ‾ ( x s m m − 1 ) = x s m ′ ′ m − 1 x_{\pi(s_m)}^{\prime m-1}=\overline{\varphi}(x_{s_m}^{m-1})=x_{s_m'}^{\prime m-1} x π ( s m ) ′ m − 1 = φ ( x s m m − 1 ) = x s m ′ ′ m − 1 , which gives s m ′ = π ( s m ) s_m'=\pi(s_m) s m ′ = π ( s m ) and hence w ′ = π ( w ) w'=\pi(w) w ′ = π ( w ) . To complete the inductive assertion, observe that, for j ≠ s m j\ne s_m j = s m , the vertex x j m − 1 x_j^{m-1} x j m − 1 survives the expansion and x j m x_j^m x j m is its unique neighbor in the new triangle. Thus φ ( x j m ) = x π ( j ) ′ m \varphi(x_j^m)=x_{\pi(j)}^{\prime m} φ ( x j m ) = x π ( j ) ′ m . The remaining vertex of the new triangle must also map to the vertex with the corresponding index. This completes the induction and proves w ∼ w ′ w\sim w' w ∼ w ′ in the first case. For the second case, let
ρ : P ( w ′ ) ⟶ P ( rev ( w ′ ) ) \rho: P(w') \longrightarrow P(\operatorname{rev}(w')) ρ : P ( w ′ ) ⟶ P ( rev ( w ′ ))
be the end-interchanging isomorphism constructed in the sufficiency proof. Then ρ ∘ φ \rho\circ\varphi ρ ∘ φ preserves the two ends individually. By the first case, there exists π ∈ S 3 \pi\in S_3 π ∈ S 3 such that rev ( w ′ ) = π ( w ) \operatorname{rev}(w') = \pi(w) rev ( w ′ ) = π ( w ) . Since reversal commutes with symbol permutations, we obtain w ′ = π ( rev ( w ) ) w' = \pi(\operatorname{rev}(w)) w ′ = π ( rev ( w )) . Hence w ∼ w ′ w \sim w' w ∼ w ′ , completing the proof.
We decompose each word w w w into a product of maximal constant blocks:
w = a 1 r 1 a 2 r 2 ⋯ a q r q , a i ≠ a i + 1 ( 1 ≤ i < q ) , r i ≥ 1 ( 1 ≤ i ≤ q ) . w = a_1^{r_1}a_2^{r_2}\cdots a_q^{r_q}, \qquad a_i \ne a_{i+1}\ (1 \le i < q), \qquad r_i \ge1\ (1 \le i \le q). w = a 1 r 1 a 2 r 2 ⋯ a q r q , a i = a i + 1 ( 1 ≤ i < q ) , r i ≥ 1 ( 1 ≤ i ≤ q ) .
The integer q q q is called the number of runs of w w w . Combining Theorems 3.2 and 3.3 with Lemma 3.5 gives a formulation independent of the choice of normalization.
Lemma 3.6. Let ∣ w ∣ ≥ 4 |w| \ge4 ∣ w ∣ ≥ 4 . Then P ( w ) ∈ U 3 ∪ U 4 P(w) \in\mathcal{U}_3 \cup\mathcal{U}_4 P ( w ) ∈ U 3 ∪ U 4 if and only if the run decomposition of w w w satisfies one of the following three conditions:
(a) q = 1 q = 1 q = 1 ;
(b) q = 2 q = 2 q = 2 , and at least one of the two end runs has length 1;
(c) q = 3 q = 3 q = 3 , the middle run has length 1, and a 1 ≠ a 3 a_1 \ne a_3 a 1 = a 3 .
Proof. By Theorem 3.3 and Lemma 3.5 , we have that constant words give the U 4 \mathcal{U}_4 U 4 family. By Lemma 3.5 , a two-run word with a one-letter end run can, after reversal and a global relabeling, be written as 1 a 3 1^a3 1 a 3 with a ≥ 3 a \ge3 a ≥ 3 , since ∣ w ∣ ≥ 4 |w| \ge4 ∣ w ∣ ≥ 4 . By Theorem 3.2 , P ( w ) ∈ U 3 P(w) \in\mathcal{U}_3 P ( w ) ∈ U 3 . In the three-run case, after reversal we may assume that the first block is at least as long as the third, and then globally relabel it as 1 a 3 2 2 b 1^{a}3^{2}2^{b} 1 a 3 2 2 b . Recall that ∣ w ∣ ≥ 4 |w| \ge4 ∣ w ∣ ≥ 4 . By Theorem 3.2 , P ( w ) ∈ U 3 P(w) \in\mathcal{U}_3 P ( w ) ∈ U 3 .
Conversely, suppose that P ( w ) ∈ U 3 ∪ U 4 P(w) \in\mathcal{U}_3 \cup\mathcal{U}_4 P ( w ) ∈ U 3 ∪ U 4 . Since ∣ w ∣ ≥ 4 |w| \ge4 ∣ w ∣ ≥ 4 , the graph P ( w ) P(w) P ( w ) has order at least 14. If P ( w ) ∈ U 4 P(w) \in\mathcal{U}_4 P ( w ) ∈ U 4 , then Theorem 3.3 excludes the exceptional graph P ( 12 ) P(12) P ( 12 ) and gives P ( w ) ≅ P ( 1 p ) P(w) \cong P(1^p) P ( w ) ≅ P ( 1 p ) for some p ≥ 2 p \ge2 p ≥ 2 . By Lemma 3.5 , w ∼ 1 p w \sim1^p w ∼ 1 p , so w w w is constant and satisfies (a).
Now suppose that P ( w ) ∈ U 3 P(w) \in\mathcal{U}_3 P ( w ) ∈ U 3 . By Lemma 3.1, P ( w ) P(w) P ( w ) has exactly two triangles, whereas each of T 0 , T 1 , T 2 , T 3 T_0,T_1,T_2,T_3 T 0 , T 1 , T 2 , T 3 has three triangles. Moreover, P ( w ) ≇ P ( 121 ) P(w) \not\cong P(121) P ( w ) ≅ P ( 121 ) , since P ( 121 ) P(121) P ( 121 ) has order 12. Thus Theorem 3.2 and Lemma 3.5 give w ∼ 1 h − 1 3 2 p − h w \sim1^{h-1}3\,2^{p-h} w ∼ 1 h − 1 3 2 p − h for some integers p , h p,h p , h satisfying p = ∣ w ∣ ≥ 4 p = |w| \ge4 p = ∣ w ∣ ≥ 4 and ( p + 1 ) / 2 ≤ h ≤ p (p+1)/2 \le h \le p ( p + 1 ) /2 ≤ h ≤ p . If h = p h = p h = p , this word has two runs, with the last run of length 1, so it satisfies (b). If h < p h < p h < p , it has three runs, the middle run has length 1, and the first and last symbols are distinct, so it satisfies (c). Since conditions (a)–(c) are preserved under reversal and global relabeling, the corresponding condition also holds for w w w . This proves necessity.
As a conclusion to this subsection, a result concerning the parent graphs of U 2 \mathcal{U}_2 U 2 primitive kernels is presented, which plays a crucial role in the classification of all U 2 \mathcal{U}_2 U 2 primitive kernels in the subsequent two subsections.
Lemma 3.7. Let C C C be a primitive U 2 \mathcal{U}_2 U 2 kernel, let T T T be any triangle of C C C , and put H = C / T H = C/T H = C / T . Then H ∈ U 3 ∪ U 4 H \in\mathcal{U}_3 \cup\mathcal{U}_4 H ∈ U 3 ∪ U 4 .
Proof. Write C = H ν C = H^\nu C = H ν . Because C ∈ U 2 C \in\mathcal{U}_2 C ∈ U 2 , C C C is a Klee graph. By [5 ] , Lemma 3.2, H H H is also a Klee graph. If H ∉ U H \notin\mathcal{U} H ∈ / U , then every edge of H ν H^\nu H ν in at least two perfect matchings: for an edge of the new triangle, use the matchings containing the opposite old edge, and for any other edge use the matchings containing its corresponding old edge. This contradicts C ∈ U 2 C \in\mathcal{U}_2 C ∈ U 2 . Hence H ∈ U H \in\mathcal{U} H ∈ U . By Proposition 2.4 , 2 = ℓ ( C ) = ℓ ( H ) − ∣ Σ H ( v ) ∣ 2 = \ell(C) = \ell(H) - |\Sigma_H(v)| 2 = ℓ ( C ) = ℓ ( H ) − ∣ Σ H ( v ) ∣ . It follows that ℓ ( H ) ≥ 2 \ell(H) \ge2 ℓ ( H ) ≥ 2 . Since C C C is a primitive U 2 \mathcal{U}_2 U 2 kernel and H = C / T H = C/T H = C / T , we have ℓ ( H ) ≥ 3 \ell(H) \ge3 ℓ ( H ) ≥ 3 . Note that Klee graphs are obtained from K 4 K_4 K 4 by expansions, and expansion never increases the number of lonely edges, so ℓ ( H ) ≤ 6 \ell(H) \le6 ℓ ( H ) ≤ 6 . To complete the proof, it suffices to show that neither ℓ ( H ) = 5 \ell(H) = 5 ℓ ( H ) = 5 nor ℓ ( H ) = 6 \ell(H) = 6 ℓ ( H ) = 6 .
By Theorem 3.4 , U 6 \mathcal{U}_6 U 6 consists only of K 4 K_4 K 4 and the triangular prism Pr \operatorname{Pr} Pr , while U 5 \mathcal{U}_5 U 5 consists only of the bicorn (see Figure 2 ). Thus, we list all their children up to isomorphism in Table 1, which shows that none of their children contains exactly two lonely edges.
Table 1. Children of graphs in U 6 \mathcal{U}_6 U 6 and U 5 \mathcal{U}_5 U 5 .
Thus, ℓ ( H ) \ell(H) ℓ ( H ) cannot be 5 or 6.
Primitive U 2 \mathcal{U}_2 U 2 kernels are divided into two distinct classes based on whether they contain exactly two triangles: those with exactly two triangles are referred to as extended-prism kernels , while the others are termed non-extended-prism kernels . The subsequent two sections are dedicated to the characterization of these two classes of primitive U 2 \mathcal{U}_2 U 2 kernels, respectively.
Primitive extended-prism U 2 \mathcal{U}_2 U 2 kernels
The primary objective of this subsection is to present a characterization of all primitive kernels in U 2 \mathcal{U}_2 U 2 that belong to the class of extended prisms.
Lemma 3.8. The primitive extended-prism U 2 \mathcal{U}_2 U 2 kernels of length four are exactly P ( 1121 ) , P ( 1122 ) , P ( 1212 ) , P ( 1213 ) , P ( 1221 ) , P ( 1223 ) , P ( 1231 ) P(1121), P(1122), P(1212), P(1213), P(1221), P(1223), P(1231) P ( 1121 ) , P ( 1122 ) , P ( 1212 ) , P ( 1213 ) , P ( 1221 ) , P ( 1223 ) , P ( 1231 ) .
Proof. Up to global relabeling and reversal, there are exactly ten patterns of length four:
1111 , 1112 , 1121 , 1122 , 1123 , 1212 , 1213 , 1221 , 1223 , 1231. 1111,\quad1112,\quad1121,\quad1122,\quad1123,\quad1212,\quad1213,\quad1221,\quad1223,\quad1231. 1111 , 1112 , 1121 , 1122 , 1123 , 1212 , 1213 , 1221 , 1223 , 1231.
To establish the validity of the conclusion, it suffices to identify all U 2 \mathcal{U}_2 U 2 graphs among these 10 extended prisms, and then prove that exactly 7 of these graphs satisfy the property that contracting any triangle results in a graph no longer belonging to U 2 \mathcal{U}_2 U 2 . By exactly enumerating all perfect matchings of the aforementioned graphs (this can be verified manually: for each selected edge, find the perfect matchings that contain it; once an edge is contained in two distinct perfect matchings, we no longer need to find all perfect matchings containing this edge. See also the Python code in [8 ] ), we can obtain the results presented in Table 2.
Note that both end contractions of each such graph yield length-three patterns, and 111 111 111 , 112 112 112 , 121 121 121 , 123 123 123 represent all length-three patterns up to global relabeling and reversal. Since all four length-three equivalence classes belong to U 3 ∪ U 4 \mathcal{U}_3 \cup\mathcal{U}_4 U 3 ∪ U 4 , all seven graphs in U 2 \mathcal{U}_2 U 2 are primitive.
For e ∈ L ( G ) e \in L(G) e ∈ L ( G ) , let M e M_e M e denote the unique perfect matching containing e e e . Put
β r = { x 1 r + 1 x 2 r + 1 , r even , x 2 r + 1 x 3 r + 1 , r odd . \beta_r =
\begin{cases}
x_1^{r+1}x_2^{r+1}, & r\ \text{even},\\
x_2^{r+1}x_3^{r+1}, & r\ \text{odd}.
\end{cases} β r = { x 1 r + 1 x 2 r + 1 , x 2 r + 1 x 3 r + 1 , r even , r odd .
Table 2. Length-four expansion patterns (m ( G ) m(G) m ( G ) : number of perfect matchings).
Lemma 3.9. For every r ≥ 2 r \ge2 r ≥ 2 , L ( P ( 12 r ) ) = { u 1 u 3 , x 2 0 x 3 0 , β r } L(P(12^{r})) = \{u_{1}u_{3},x_{2}^{0}x_{3}^{0},\beta_{r}\} L ( P ( 1 2 r )) = { u 1 u 3 , x 2 0 x 3 0 , β r } . Moreover, M u 1 u 3 = M β r ≠ M x 2 0 x 3 0 M_{u_{1}u_{3}} = M_{\beta_{r}} \ne M_{x_{2}^{0}x_{3}^{0}} M u 1 u 3 = M β r = M x 2 0 x 3 0 and the three vertices of the active end satisfy
Σ P ( 12 r ) ( x 1 r + 1 ) = { { x 2 0 x 3 0 } , r even , { u 1 u 3 } , r odd , (3) \Sigma_{P(12^{r})}(x_{1}^{r+1}) =
\begin{cases}
\{x_{2}^{0}x_{3}^{0}\}, & r\ \text{even},\\
\{u_{1}u_{3}\}, & r\ \text{odd},
\end{cases} \tag*{(3)} Σ P ( 1 2 r ) ( x 1 r + 1 ) = { { x 2 0 x 3 0 } , { u 1 u 3 } , r even , r odd , (3) Σ P ( 12 r ) ( x 2 r + 1 ) = ∅ , (4) \Sigma_{P(12^{r})}(x_{2}^{r+1}) = \varnothing, \tag*{(4)} Σ P ( 1 2 r ) ( x 2 r + 1 ) = ∅ , (4) Σ P ( 12 r ) ( x 3 r + 1 ) = { { u 1 u 3 } , r even , { x 2 0 x 3 0 } , r odd . (5) \Sigma_{P(12^{r})}(x_{3}^{r+1}) =
\begin{cases}
\{u_{1}u_{3}\}, & r\ \text{even},\\
\{x_{2}^{0}x_{3}^{0}\}, & r\ \text{odd}.
\end{cases} \tag*{(5)} Σ P ( 1 2 r ) ( x 3 r + 1 ) = { { u 1 u 3 } , { x 2 0 x 3 0 } , r even , r odd . (5)
Proof. By Lemma 3.5 , we have P ( 12 r ) ≅ P ( 2 r 1 ) ≅ P ( 1 r 32 0 ) P(12^{r}) \cong P(2^{r}1) \cong P(1^{r}32^{0}) P ( 1 2 r ) ≅ P ( 2 r 1 ) ≅ P ( 1 r 3 2 0 ) . By Theorem 3.2 , P ( 12 r ) ∈ U 3 P(12^{r}) \in U_{3} P ( 1 2 r ) ∈ U 3 , so it is enough to identify three lonely edges.
First fix u 1 u 3 u_{1}u_{3} u 1 u 3 . The vertex u 2 u_{2} u 2 is forced to match x 2 0 x_{2}^{0} x 2 0 , which in turn forces x 3 0 x_{3}^{0} x 3 0 to match x 3 1 x_{3}^{1} x 3 1 . Continuing along the two ladder tracks forces the matching edges successively to be
x 1 1 x 1 2 , x 3 2 x 3 3 , x 1 2 x 1 4 , x 3 3 x 3 4 , x 1 4 x 1 5 , … , x_{1}^{1}x_{1}^{2},\ x_{3}^{2}x_{3}^{3},\ x_{1}^{2}x_{1}^{4},\ x_{3}^{3}x_{3}^{4},\ x_{1}^{4}x_{1}^{5},\ldots, x 1 1 x 1 2 , x 3 2 x 3 3 , x 1 2 x 1 4 , x 3 3 x 3 4 , x 1 4 x 1 5 , … ,
and the last two unmatched vertices at the active end are joined precisely by β r \beta_{r} β r . Thus the perfect matching containing u 1 u 3 u_{1}u_{3} u 1 u 3 is unique and also contains β r \beta_{r} β r . Running the same forcing argument backward from the right end shows that the perfect matching containing β r \beta_{r} β r must be this same matching. Thus, M u 1 u 3 = M β r M_{u_{1}u_{3}} = M_{\beta_{r}} M u 1 u 3 = M β r .
If instead x 2 0 x 3 0 x_{2}^{0}x_{3}^{0} x 2 0 x 3 0 is fixed, then the left end is forced to use u 2 u 3 u_{2}u_{3} u 2 u 3 and u 1 x 1 1 u_{1}x_{1}^{1} u 1 x 1 1 . The forced track then becomes
x 3 1 x 3 2 , x 1 2 x 1 3 , x 3 3 x 3 4 , x 1 4 x 1 5 , … , x_{3}^{1}x_{3}^{2},\ x_{1}^{2}x_{1}^{3},\ x_{3}^{3}x_{3}^{4},\ x_{1}^{4}x_{1}^{5},\ldots, x 3 1 x 3 2 , x 1 2 x 1 3 , x 3 3 x 3 4 , x 1 4 x 1 5 , … ,
and terminates at the active end with the edge between the two remaining vertices. Hence M x 2 0 x 3 0 M_{x_{2}^{0}x_{3}^{0}} M x 2 0 x 3 0 is also unique; it does not contain u 1 u 3 u_{1}u_{3} u 1 u 3 at the left end, so it is different from M u 1 u 3 M_{u_{1}u_{3}} M u 1 u 3 . Since P ( 12 r ) ∈ U 3 P(12^{r}) \in U_{3} P ( 1 2 r ) ∈ U 3 , these three edges are all the lonely edges.
Finally consider joins rooted at a vertex of the active end. First let the root be v = x j r + 1 v=x_{j}^{r+1} v = x j r + 1 , where j ∈ { 1 , 3 } j \in\{1,3\} j ∈ { 1 , 3 } , and put q = 4 − j q=4-j q = 4 − j . The three edges incident with v v v are selected. In particular, the other two vertices of the active-end triangle already have degree 1, so x 2 0 x 2 r + 1 x_{2}^{0}x_{2}^{r+1} x 2 0 x 2 r + 1 and x q r x q r + 1 x_{q}^{r}x_{q}^{r+1} x q r x q r + 1 are excluded. The edge β r \beta_{r} β r either is incident with v v v or joins the other two vertices of the triangle; in the latter case it cannot be selected. Thus β r ∉ Σ P ( 12 r ) ( v ) \beta_{r} \notin\Sigma_{P(12^{r})}(v) β r ∈ / Σ P ( 1 2 r ) ( v ) .
The selected rail edge x j r x j r + 1 x_{j}^{r}x_{j}^{r+1} x j r x j r + 1 determines the rail choices backward through the internal rungs. Indeed, at each rung x 1 k x 3 k x_{1}^{k}x_{3}^{k} x 1 k x 3 k (1 ≤ k ≤ r 1 \le k \le r 1 ≤ k ≤ r ), exactly one selected edge enters from the right. Its endpoint already has degree 1, so the rung is excluded and the other endpoint must use its left rail edge. Consequently, the selected rail switches at each rung. At the left boundary, the selected edge is u 1 x 1 1 u_{1}x_{1}^{1} u 1 x 1 1 precisely when j = 1 j=1 j = 1 and r r r is even or j = 3 j=3 j = 3 and r r r is odd; in the other two cases it is x 3 0 x 3 1 x_{3}^{0}x_{3}^{1} x 3 0 x 3 1 .
If u 1 x 1 1 u_{1}x_{1}^{1} u 1 x 1 1 is selected, then u 1 u 3 u_{1}u_{3} u 1 u 3 is excluded. Since x 2 0 x 2 r + 1 x_{2}^{0}x_{2}^{r+1} x 2 0 x 2 r + 1 and x 2 0 x 1 1 x_{2}^{0}x_{1}^{1} x 2 0 x 1 1 are also excluded, the remaining four vertices at the left end can be covered by either { u 2 u 3 , x 2 0 x 3 0 } \{u_{2}u_{3},x_{2}^{0}x_{3}^{0}\} { u 2 u 3 , x 2 0 x 3 0 } or { u 2 x 2 0 , u 3 x 3 0 } \{u_{2}x_{2}^{0},u_{3}x_{3}^{0}\} { u 2 x 2 0 , u 3 x 3 0 } . The first choice gives a join containing x 2 0 x 3 0 x_2^0x_3^0 x 2 0 x 3 0 . If x 3 0 x 3 1 x_3^0x_3^1 x 3 0 x 3 1 is selected instead, then x 2 0 x 3 0 x_2^0x_3^0 x 2 0 x 3 0 is excluded, and the degree requirements force u 2 x 2 0 u_2x_2^0 u 2 x 2 0 and u 1 u 3 u_1u_3 u 1 u 3 . In each case, the indicated left-end edges, the alternating rail edges and the three edges incident with v v v give a spanning subgraph in which v v v has degree 3 and every other vertex has degree 1. This proves both the existence of a join containing the stated lonely edge and the exclusion of the other nonincident lonely edges. Hence (3) and (5) hold.
For the middle root x 2 r + 1 x_2^{r+1} x 2 r + 1 , every join contains x 2 0 x 2 r + 1 x_2^0x_2^{r+1} x 2 0 x 2 r + 1 , so it cannot contain x 2 0 x 3 0 x_2^0x_3^0 x 2 0 x 3 0 . It cannot contain u 1 u 3 u_1u_3 u 1 u 3 either, since that would force u 2 x 2 0 u_2x_2^0 u 2 x 2 0 and give the non-root x 2 0 x_2^0 x 2 0 degree 2. The remaining lonely edge β r \beta_r β r is incident with the root and therefore does not belong to its loss set. This proves (4) .
Define U 2 = = { G ∈ U 2 : M α = M β } \mathcal{U}_2^{=}=\{G\in\mathcal{U}_2:M_\alpha=M_\beta\} U 2 = = { G ∈ U 2 : M α = M β } , U 2 ≠ = { G ∈ U 2 : M α ≠ M β } \mathcal{U}_2^{\ne}=\{G\in\mathcal{U}_2:M_\alpha\ne M_\beta\} U 2 = = { G ∈ U 2 : M α = M β } where L ( G ) = { α , β } L(G)=\{\alpha,\beta\} L ( G ) = { α , β } . Let M M M be a perfect matching of G G G containing v x vx v x , where N G ( v ) = { x , y , z } N_G(v)=\{x,y,z\} N G ( v ) = { x , y , z } . Define its natural lift by
M ^ v = ( M ∖ { v x } ) ∪ { v x x , v y v z } . (6) \widehat{M}^{\,v}=(M\setminus\{vx\})\cup\{v_xx,v_yv_z\}. \tag*{(6)} M v = ( M ∖ { v x }) ∪ { v x x , v y v z } . (6)
Corollary 3.10. For every r ≥ 2 r\ge2 r ≥ 2 , both P ( 12 r 1 ) P(12^r1) P ( 1 2 r 1 ) and P ( 12 r 3 ) P(12^r3) P ( 1 2 r 3 ) belong to U 2 \mathcal{U}_2 U 2 . Their types are
Proof. The graph P ( 12 r 1 ) P(12^r1) P ( 1 2 r 1 ) is obtained by expanding P ( 12 r ) P(12^r) P ( 1 2 r ) at x 1 r + 1 x_1^{r+1} x 1 r + 1 , and P ( 12 r 3 ) P(12^r3) P ( 1 2 r 3 ) by expanding at x 3 r + 1 x_3^{r+1} x 3 r + 1 . By Proposition 2.4 and Lemma 3.9 , each expansion loses exactly one lonely edge, so the resulting graph lies in U 2 \mathcal{U}_2 U 2 . The unique perfect matching of each surviving lonely edge is the natural lift of the corresponding original unique perfect matching. Combining M u 1 u 3 = M β r ≠ M x 2 0 x 3 0 M_{u_1u_3}=M_{\beta_r}\ne M_{x_2^0x_3^0} M u 1 u 3 = M β r = M x 2 0 x 3 0 with (3) and (5) gives the parity classification in the table immediately.
Theorem 3.11. The primitive extended-prism U 2 \mathcal{U}_2 U 2 kernels are exactly
E 2 = { P ( 1121 ) , P ( 1122 ) , P ( 1212 ) , P ( 1213 ) , P ( 1231 ) } ∪ { P ( 12 r 1 ) , P ( 12 r 3 ) : r ≥ 2 } . \mathcal{E}_2=\{P(1121),P(1122),P(1212),P(1213),P(1231)\}\cup\{P(12^r1),P(12^r3):r\ge2\}. E 2 = { P ( 1121 ) , P ( 1122 ) , P ( 1212 ) , P ( 1213 ) , P ( 1231 )} ∪ { P ( 1 2 r 1 ) , P ( 1 2 r 3 ) : r ≥ 2 } . Proof. First we show that all listed graphs are primitive. The five isolated patterns and the two cases P ( 1221 ) P(1221) P ( 1221 ) , P ( 1223 ) P(1223) P ( 1223 ) with r = 2 r=2 r = 2 follow from Lemma 3.8 . Let r ≥ 3 r\ge3 r ≥ 3 . By Corollary 3.10, P ( 12 r 1 ) , P ( 12 r 3 ) ∈ U 2 P(12^r1),P(12^r3)\in\mathcal{U}_2 P ( 1 2 r 1 ) , P ( 1 2 r 3 ) ∈ U 2 . Each has only the two end triangles. Contracting the right end gives P ( 12 r ) ∈ U 3 P(12^r)\in\mathcal{U}_3 P ( 1 2 r ) ∈ U 3 ; after contracting the left end, the resulting pattern is t 2 r t2^r t 2 r with t = 1 t=1 t = 1 or 3 3 3 , which after a global relabeling is also equivalent to 12 r 12^r 1 2 r . Thus this parent also belongs to U 3 \mathcal{U}_3 U 3 . Hence neither graph has a U 2 \mathcal{U}_2 U 2 parent, and both are primitive.
For completeness, let C = P ( w ) C=P(w) C = P ( w ) be a primitive extended-prism U 2 \mathcal{U}_2 U 2 kernel, with m = ∣ w ∣ m=|w| m = ∣ w ∣ . By the proof of Lemma 3.8 , extended prisms of length at most three lie in U 6 , U 5 , U 4 \mathcal{U}_6,\mathcal{U}_5,\mathcal{U}_4 U 6 , U 5 , U 4 , or U 3 \mathcal{U}_3 U 3 . It follows that m ≥ 4 m\ge4 m ≥ 4 . If m = 4 m=4 m = 4 , Lemma 3.8 gives seven patterns, exactly the five isolated patterns listed in the theorem together with the two family members at r = 2 r=2 r = 2 .
Now suppose m ≥ 5 m\ge5 m ≥ 5 . By primitivity and Lemma 3.7 , both parent graphs obtained by contracting an end triangle belong to U 3 ∪ U 4 \mathcal{U}_3\cup\mathcal{U}_4 U 3 ∪ U 4 . By Lemma 3.1(2), this is equivalent to stating that both the length-( m − 1 ) (m-1) ( m − 1 ) prefix and suffix of the corresponding word satisfy the conditions specified in Lemma 3.6 . Notably, the full word w w w cannot satisfy this language; if it did, C C C would belong to U 3 ∪ U 4 \mathcal{U}_3\cup\mathcal{U}_4 U 3 ∪ U 4 , which contradicts the assumption that C ∈ U 2 C\in\mathcal{U}_2 C ∈ U 2 . With this in mind, we claim that w ∼ 12 m − 2 1 w\sim12^{m-2}1 w ∼ 1 2 m − 2 1 or w ∼ 12 m − 2 3 w\sim12^{m-2}3 w ∼ 1 2 m − 2 3 .
To justify this claim, we begin by considering the run decomposition of w w w : w = a 1 r 1 ⋯ a q r q w=a_1^{r_1}\cdots a_q^{r_q} w = a 1 r 1 ⋯ a q r q . Deleting either the first or last letter of w w w removes at most one terminal run from this decomposition. Given that both the prefix w − = a 1 r 1 ⋯ a q − 1 r q − 1 a q r q − 1 w^-=a_1^{r_1}\cdots a_{q-1}^{r_{q-1}}a_q^{r_q-1} w − = a 1 r 1 ⋯ a q − 1 r q − 1 a q r q − 1 and suffix w + = a 1 r 1 − 1 a 2 r 2 ⋯ a q r q w^+=a_1^{r_1-1}a_2^{r_2}\cdots a_q^{r_q} w + = a 1 r 1 − 1 a 2 r 2 ⋯ a q r q
contain at most three runs, it immediately follows that q ≤ 4 q \le4 q ≤ 4 . Furthermore, since w w w itself does not satisfy the language defined in Lemma 3.6 , we can conclude that q ≥ 2 q \ge2 q ≥ 2 .
Suppose q = 4 q = 4 q = 4 . In order for deletion of either the first or last letter to leave at most three runs, we must have r 1 = r 4 = 1 r_1 = r_4 = 1 r 1 = r 4 = 1 . The three run lengths of w − w^{-} w − are then ( 1 , r 2 , r 3 ) (1, r_2, r_3) ( 1 , r 2 , r 3 ) , and Lemma 3.6 (c) gives r 2 = 1 r_2 = 1 r 2 = 1 ; similarly w + w^{+} w + gives r 3 = 1 r_3 = 1 r 3 = 1 . Thus m = 4 m = 4 m = 4 , contradicting m ≥ 5 m \ge5 m ≥ 5 .
Suppose q = 2 q = 2 q = 2 . Note that w w w does not satisfy Lemma 3.6 (b). We find that r 1 , r 2 ≥ 2 r_1, r_2 \ge2 r 1 , r 2 ≥ 2 . The run lengths of the suffix are ( r 1 − 1 , r 2 ) (r_1 - 1, r_2) ( r 1 − 1 , r 2 ) , and one of its end runs must have length 1 1 1 , so r 1 = 2 r_1 = 2 r 1 = 2 . Similarly the prefix forces r 2 = 2 r_2 = 2 r 2 = 2 , again giving m = 4 m = 4 m = 4 , a contradiction.
Suppose q = 3 q = 3 q = 3 . If r 1 > 1 r_1 > 1 r 1 > 1 and r 3 > 1 r_3 > 1 r 3 > 1 , then both the prefix and suffix still have three runs, and both force r 2 = 1 r_2 = 1 r 2 = 1 and a 1 ≠ a 3 a_1 \ne a_3 a 1 = a 3 , so w w w itself satisfies Lemma 3.6 (c), a contradiction. Hence at least one end run has length 1 1 1 . Without loss of generality, let r 1 = 1 r_1 = 1 r 1 = 1 . If r 3 > 1 r_3 > 1 r 3 > 1 , then the prefix still has three runs and again forces r 2 = 1 r_2 = 1 r 2 = 1 and a 1 ≠ a 3 a_1 \ne a_3 a 1 = a 3 , so w w w satisfies the condition, a contradiction. Thus r 3 = 1 r_3 = 1 r 3 = 1 . Symmetrically, r 3 = 1 r_3 = 1 r 3 = 1 also forces r 1 = 1 r_1 = 1 r 1 = 1 . Therefore, w = a 1 a 2 m − 2 a 3 w = a_1a_2^{m-2}a_3 w = a 1 a 2 m − 2 a 3 , a 1 ≠ a 2 a_1 \ne a_2 a 1 = a 2 , a 3 ≠ a 2 a_3 \ne a_2 a 3 = a 2 . If a 1 = a 3 a_1 = a_3 a 1 = a 3 , a global relabeling gives 12 m − 2 1 12^{m-2}1 1 2 m − 2 1 ; if a 1 ≠ a 3 a_1 \ne a_3 a 1 = a 3 , the three symbols are distinct, and a global relabeling gives 12 m − 2 3 12^{m-2}3 1 2 m − 2 3 .
Putting r = m − 2 ≥ 3 r = m - 2 \ge3 r = m − 2 ≥ 3 gives the two infinite families. This proves completeness.
Primitive non-extended-prism kernels
In this subsection, a characterization of primitive non-extended-prism U 2 \mathcal{U}_2 U 2 kernels is presented.
Let D 0 , D 1 , D 2 , T 0 , T 1 , T 2 , T 3 D_0, D_1, D_2, T_0, T_1, T_2, T_3 D 0 , D 1 , D 2 , T 0 , T 1 , T 2 , T 3 be the graphs shown in Figure 3 and Figure 4 . Dashed edges in the figures are lonely edges. Direct computation gives
Figure 4. The three primitive kernels that are not extended prisms.
L ( T i ) = { ( 1 , 3 ) , ( 4 , 8 ) , ( 6 , 7 ) } ( 0 ≤ i ≤ 3 ) , (7) L(T_i) = \{(1,3), (4,8), (6,7)\} \qquad(0 \le i \le3), \tag*{(7)} L ( T i ) = {( 1 , 3 ) , ( 4 , 8 ) , ( 6 , 7 )} ( 0 ≤ i ≤ 3 ) , (7)
and
L ( D 0 ) = { ( 1 , 10 ) , ( 4 , 8 ) } , L ( D 1 ) = { ( 1 , 3 ) , ( 4 , 8 ) } , L ( D 2 ) = { ( 1 , 3 ) , ( 6 , 7 ) } . (8) L(D_0) = \{(1,10), (4,8)\},\quad L(D_1) = \{(1,3), (4,8)\},\quad L(D_2) = \{(1,3), (6,7)\}. \tag*{(8)} L ( D 0 ) = {( 1 , 10 ) , ( 4 , 8 )} , L ( D 1 ) = {( 1 , 3 ) , ( 4 , 8 )} , L ( D 2 ) = {( 1 , 3 ) , ( 6 , 7 )} . (8)
Lemma 3.12. The set consisting of all children of T 0 , T 1 , T 2 , T 3 T_0, T_1, T_2, T_3 T 0 , T 1 , T 2 , T 3 that are primitive U 2 \mathcal{U}_2 U 2 kernels is { D 0 , D 1 , D 2 } \{D_0, D_1, D_2\} { D 0 , D 1 , D 2 } .
Proof. The idea of the proof is relatively simple, as follows. For each vertex v i j ∈ V ( T i ) v_{ij} \in V(T_i) v ij ∈ V ( T i ) , where i ∈ { 0 , 1 , 2 , 3 } i \in\{0, 1, 2, 3\} i ∈ { 0 , 1 , 2 , 3 } and 1 ≤ j ≤ ∣ V ( T i ) ∣ 1 \le j \le|V(T_i)| 1 ≤ j ≤ ∣ V ( T i ) ∣ , we first enumerate the perfect matchings of T i v i j T_i^{v_{ij}} T i v ij to determine its number of lonely edges. For this purpose, the number of perfect matchings containing each edge only needs to be counted up to two. We retain only those graphs having exactly two lonely edges. For each retained graph, we then contract each triangle separately and determine the number of lonely edges in the resulting graph. If any such contraction yields a graph with exactly two lonely edges, the original graph is discarded; otherwise, it is a primitive U 2 U_2 U 2 kernel. Finally, we remove isomorphic duplicates, retaining one representative from each isomorphism class. Since this verification involves numerous cases, we provide an algorithmic verification in [8 ] .
Lemma 3.13. [5 ] A graph G ∈ U 3 G \in U_3 G ∈ U 3 has exactly three triangles if and only if G G G is isomorphic to one of T 0 , T 1 , T 2 , T 3 T_0,T_1,T_2,T_3 T 0 , T 1 , T 2 , T 3 . Moreover, every Klee graph of order at least 10 with exactly three triangles is isomorphic to T 0 T_0 T 0 or to a descendant of T 0 T_0 T 0 .
Theorem 3.14. The primitive U 2 U_2 U 2 kernels that are not extended prisms are exactly D 0 , D 1 , D 2 D_0,D_1,D_2 D 0 , D 1 , D 2 .
Proof. Note that each graph in { D 0 , D 1 , D 2 } \{D_0,D_1,D_2\} { D 0 , D 1 , D 2 } has three triangles and therefore is not an extended prism. By Lemma 3.12, D 0 , D 1 , D 2 D_0,D_1,D_2 D 0 , D 1 , D 2 are primitive non-extended-prism U 2 U_2 U 2 kernels.
Conversely, let C C C be a primitive U 2 U_2 U 2 kernel that is not an extended prism. By Lemma 3.1, C C C has at least three triangles. By Lemma 3.7 , every triangle-contraction parent of C C C belongs to U 3 ∪ U 4 U_3 \cup U_4 U 3 ∪ U 4 . According to Theorems 3.2 and 3.3 , graphs in U 4 U_4 U 4 have exactly two triangles and graphs in U 3 U_3 U 3 have at most three. Therefore C C C has at most four triangles: contracting one triangle reduces the number of triangles by at most one, while the parent has at most three.
If C C C has exactly three triangles, then by Lemma 3.13 it is a descendant of T 0 T_0 T 0 . Choose a shortest expansion sequence from T 0 T_0 T 0 to C C C , and let H H H be the penultimate graph. Then H H H is a triangle-contraction parent of C C C , so H ∈ U 3 ∪ U 4 H \in U_3 \cup U_4 H ∈ U 3 ∪ U 4 . As a descendant of T 0 T_0 T 0 , the graph H H H has at least three triangles, so H ∉ U 4 H \notin U_4 H ∈ / U 4 and hence H ∈ U 3 H \in U_3 H ∈ U 3 . By Lemma 3.13, H ∈ { T 0 , T 1 , T 2 , T 3 } H \in\{T_0,T_1,T_2,T_3\} H ∈ { T 0 , T 1 , T 2 , T 3 } , and therefore C C C is a child of some T i T_i T i . By Lemma 3.12, C ∈ { D 0 , D 1 , D 2 } C \in\{D_0,D_1,D_2\} C ∈ { D 0 , D 1 , D 2 } .
If C C C has exactly four triangles, then contracting any triangle gives a parent with at least three triangles. Since the parent has at most three, it is a U 3 U_3 U 3 graph with exactly three triangles and hence again belongs to { T 0 , T 1 , T 2 , T 3 } \{T_0,T_1,T_2,T_3\} { T 0 , T 1 , T 2 , T 3 } . Thus C C C is again a child of some T i T_i T i . By Lemma 3.12, C ∈ { D 0 , D 1 , D 2 } C \in\{D_0,D_1,D_2\} C ∈ { D 0 , D 1 , D 2 } . This contradicts the fact that each D i D_i D i has exactly three triangles. Hence this case cannot occur.
Characterization of U 2 U_2 U 2
In this section, we will provide a complete characterization of U 2 U_2 U 2 using mathematical induction. As preliminary preparation, we first introduce two lemmas.
Lemma 4.1. Suppose L ( G ) = { α , β } L(G)=\{\alpha,\beta\} L ( G ) = { α , β } and G v ∈ U 2 G^v \in U_2 G v ∈ U 2 . Then M α = M β ⟺ M λ v ( α ) = M λ v ( β ) M_\alpha=M_\beta\Longleftrightarrow M_{\lambda_v(\alpha)}=M_{\lambda_v(\beta)} M α = M β ⟺ M λ v ( α ) = M λ v ( β ) .
Proof. By Proposition 2.4 , after a zero-loss expansion the two lonely edges are exactly λ v ( α ) \lambda_v(\alpha) λ v ( α ) and λ v ( β ) \lambda_v(\beta) λ v ( β ) . Contracting the new triangle in a perfect matching containing either transferred edge gives a perfect matching containing the corresponding original lonely edge. The original lonely edge belongs to only one perfect matching, and (6) gives its unique lift. The equivalence follows immediately. □
Lemma 4.2. Let v v v be a zero-loss expansion vertex of G G G where G ∈ U 2 G \in\mathcal{U}_2 G ∈ U 2 . For x ∈ N G ( v ) x \in N_G(v) x ∈ N G ( v ) , the new vertex v x v_x v x is zero-loss expandable in G v G^v G v if and only if, for every lonely edge e e e not incident with v v v , v x ∉ M e v_x \notin M_e v x ∈ / M e .
Proof. Put N G ( v ) = { x , y , z } N_G(v)=\{x,y,z\} N G ( v ) = { x , y , z } and H = G v H=G^v H = G v . A join rooted at v x v_x v x contains v x x , v x v y , v x v z v_xx,v_xv_y,v_xv_z v x x , v x v y , v x v z . Hence it contains neither v y y v_yy v y y nor v z z v_zz v z z nor v y v z v_yv_z v y v z . Deleting its two triangle edges and contracting the new triangle therefore gives a perfect matching of G G G containing v x vx v x . Conversely, a perfect matching M M M of G G G containing v x vx v x gives such a join with edge set ( M ∖ { v x } ) ∪ { v x x , v x v y , v x v z } (M\setminus\{vx\})\cup\{v_xx,v_xv_y,v_xv_z\} ( M ∖ { v x }) ∪ { v x x , v x v y , v x v z } . By Proposition 2.4 , every lonely edge of H H H is the transfer of a lonely edge of G G G , since v v v is zero-loss expandable. A transferred edge from an old lonely edge incident with v v v either is incident with v x v_x v x or equals v y v z v_yv_z v y v z , which the join cannot contain. Thus a v x v_x v x -rooted join contains a lonely edge not incident with v x v_x v x if and only if there is an e ∈ L ( G ) e\in L(G) e ∈ L ( G ) not incident with v v v such that v x ∈ M e v_x\in M_e v x ∈ M e . Taking the negation gives the assertion. □
R-join and its property
Definition 4.3. Let R ⊆ V ( G ) R\subseteq V(G) R ⊆ V ( G ) . An R R R -join is a spanning subgraph J J J of G G G such that
d J ( u ) = 3 ( u ∈ R ) , d J ( u ) = 1 ( u ∉ R ) . d_J(u)=3 \quad(u\in R),\qquad d_J(u)=1 \quad(u\notin R). d J ( u ) = 3 ( u ∈ R ) , d J ( u ) = 1 ( u ∈ / R ) .
Let Act ( G ) = { v ∈ V ( G ) : Σ G ( v ) = ∅ } \operatorname{Act}(G)=\{v\in V(G):\Sigma_G(v)=\varnothing\} Act ( G ) = { v ∈ V ( G ) : Σ G ( v ) = ∅ } denote the set of all zero-loss expansion vertices of G ∈ U 2 G\in\mathcal{U}_2 G ∈ U 2 . For A ⊆ V ( G ) A\subseteq V(G) A ⊆ V ( G ) , we say that A A A has the noninterference property if, for every nonempty R ⊆ A R\subseteq A R ⊆ A and every lonely edge e e e with V ( e ) ∩ R = ∅ V(e)\cap R=\varnothing V ( e ) ∩ R = ∅ , there is no R R R -join containing e e e (when R = { v } R=\{v\} R = { v } , this says exactly that v v v is a zero-loss expansion vertex).
Proposition 4.4. Suppose G ∈ U 2 G\in\mathcal{U}_2 G ∈ U 2 and suppose Act ( G ) \operatorname{Act}(G) Act ( G ) has the noninterference property . Choose v ∈ Act ( G ) v\in\operatorname{Act}(G) v ∈ Act ( G ) and put H = G v H=G^v H = G v . Define B v = { u ∈ Act ( G ) ∖ { v } : u v ∈ L ( G ) } B_v=\{u\in\operatorname{Act}(G)\setminus\{v\}:uv\in L(G)\} B v = { u ∈ Act ( G ) ∖ { v } : uv ∈ L ( G )} and T v = { v x : x ∈ N G ( v ) , v x ∉ M e for every e ∈ L ( G ) not incident with v } T_v=\{v_x:x\in N_G(v),v_x\notin M_e\text{ for every }e\in L(G)\text{ not incident with }v\} T v = { v x : x ∈ N G ( v ) , v x ∈ / M e for every e ∈ L ( G ) not incident with v } . Then Act ( H ) = ( Act ( G ) ∖ ( { v } ∪ B v ) ) ∪ T v \operatorname{Act}(H)=(\operatorname{Act}(G)\setminus(\{v\}\cup B_v))\cup T_v Act ( H ) = ( Act ( G ) ∖ ({ v } ∪ B v )) ∪ T v , and Act ( H ) \operatorname{Act}(H) Act ( H ) again has the noninterference property .
Proof. First determine which old vertices remain zero-loss expandable in G v G^v G v . If u ∉ Act ( G ) u\notin\operatorname{Act}(G) u ∈ / Act ( G ) , choose a u u u -rooted join containing a lonely edge not incident with u u u . At v v v this join uses one incident edge; replacing that edge by the corresponding external edge and opposite edge gives the same witness in H H H , so u u u remains not zero-loss expandable.
Now let u ∈ Act ( G ) ∖ { v } u\in\operatorname{Act}(G)\setminus\{v\} u ∈ Act ( G ) ∖ { v } . If u v uv uv is a lonely edge, a u u u -rooted join exists by [5 Lemma 3.4] , and every such join contains u v uv uv . Lifting it to H H H makes the join contain the transferred opposite edge of u v uv uv , which is no longer incident with u u u , so u u u ceases to be zero-loss expandable. These are exactly the vertices in B v B_v B v . Suppose instead that u v uv uv is not lonely. We claim that every u u u -rooted join in H H H contains no lonely edges not incident with u u u .
Suppose, to the contrary, that H H H has a u u u -rooted join containing a lonely edge not incident with u u u . On the new triangle, the join has one of two forms. If it uses one triangle edge, contraction yields a u u u -rooted join in G G G containing the corresponding lonely edge. This edge is still not incident with u u u , because u v uv uv is not lonely, contradicting u ∈ Act ( G ) u\in\operatorname{Act}(G) u ∈ Act ( G ) . If it uses no triangle edge, then all three external edges are used, and contraction yields a { u , v } \{u,v\} { u , v } -join in G G G containing the same lonely edge. That lonely edge is incident with neither u u u (by its choice) nor v v v (by Corollary 2.6 and the absence of selected triangle edges); this contradicts noninterference of Act ( G ) \operatorname{Act}(G) Act ( G ) . By the claim above, a vertex u u u such that u v uv uv is not a lonely edge remains zero-loss expandable in G v G^v G v . By Lemma 4.2 , the new-triangle vertices in T v T_v T v belong to Act ( H ) \operatorname{Act}(H) Act ( H ) . This proves that Act ( H ) = ( Act ( G ) ∖ ( { v } ∪ B v ) ) ∪ T v \operatorname{Act}(H) = (\operatorname{Act}(G) \setminus(\{v\} \cup B_v)) \cup T_v Act ( H ) = ( Act ( G ) ∖ ({ v } ∪ B v )) ∪ T v .
It remains to prove noninterference of Act ( H ) \operatorname{Act}(H) Act ( H ) . Suppose, to the contrary, that for some nonempty R ′ ⊆ Act ( H ) R' \subseteq\operatorname{Act}(H) R ′ ⊆ Act ( H ) there is an R ′ R' R ′ -join containing a lonely edge not incident with R ′ R' R ′ . Let T T T be the new triangle, and let k k k be the number of roots of R ′ R' R ′ in T T T . If k = 2 k = 2 k = 2 , both roots must select all three of their incident edges, so the third new vertex receives at least two selected triangle edges and has degree at least 2, impossible for a non-root.
If k = 0 k = 0 k = 0 , then on the new triangle the join either uses one triangle edge, in which case contraction gives an R ′ R' R ′ -join in G G G , or it uses all three external edges, in which case contraction gives an ( R ′ ∪ { v } ) (R' \cup\{v\}) ( R ′ ∪ { v }) -join. In the first case, if the contained lonely edge is the transfer of v x ∈ L ( G ) vx \in L(G) v x ∈ L ( G ) , then x ∉ R ′ x \notin R' x ∈ / R ′ : otherwise x ∈ B v x \in B_v x ∈ B v , whereas B v ∩ Act ( H ) = ∅ B_v \cap\operatorname{Act}(H) = \varnothing B v ∩ Act ( H ) = ∅ . Thus the corresponding old lonely edge is still nonincident with R ′ R' R ′ . In the second case, the contained lonely edge lies outside the new triangle and, by Corollary 2.6, is not an external edge, so it remains nonincident with R ′ ∪ { v } R' \cup\{v\} R ′ ∪ { v } . Both cases contradict noninterference of Act ( G ) \operatorname{Act}(G) Act ( G ) .
If k = 1 k = 1 k = 1 , let the unique new root be v x v_x v x . The contained lonely edge lies outside the new triangle: its only edge not incident with v x v_x v x cannot be selected in a v x v_x v x -rooted join, and external edges are not lonely. Delete its two triangle edges and contract the new triangle. This yields an ( R ′ ∖ { v x } ) (R' \setminus\{v_x\}) ( R ′ ∖ { v x }) -join in G G G that is forced to use v x vx v x . If the old root set is nonempty, this again contradicts noninterference of Act ( G ) \operatorname{Act}(G) Act ( G ) . If the old root set is empty, we obtain a perfect matching containing the lonely edge and using v x vx v x , which must be the corresponding unique perfect matching M e M_e M e ; this contradicts v x ∈ T v v_x \in T_v v x ∈ T v .
If k = 3 k = 3 k = 3 , the three new roots force all three triangle edges and all three external edges to be selected. Contracting the new triangle gives a ( ( R ′ ∖ V ( T ) ) ∪ { v } ) ((R' \setminus V(T)) \cup\{v\}) (( R ′ ∖ V ( T )) ∪ { v }) -join in G G G . Since the contained lonely edge is incident with none of the three new roots, it cannot be the transfer of a lonely edge incident with v v v , and after contraction it remains nonincident with every root. This again contradicts noninterference of Act ( G ) \operatorname{Act}(G) Act ( G ) . All four cases are impossible, so Act ( H ) \operatorname{Act}(H) Act ( H ) remains noninterfering.
Two standard markings and three expansion operations
Definition 4.5. Let G ∈ U 2 G \in\mathcal{U}_2 G ∈ U 2 . A marked object B = ( G ; a b , d e ; a b c , d e f ) \mathcal{B} = (G; ab, de; abc, def) B = ( G ; ab , d e ; ab c , d e f ) is called an equal-matching standard marking if the following hold:
(E1) L ( G ) = { a b , d e } L(G) = \{ab, de\} L ( G ) = { ab , d e } and M a b = M d e M_{ab} = M_{de} M ab = M d e ;
(E2) a b c abc ab c and d e f def d e f are triangles of G G G ;
(E3) Act ( G ) = { a , b , d , e } \operatorname{Act}(G) = \{a, b, d, e\} Act ( G ) = { a , b , d , e } .
Lemma 4.6. If B = ( G ; a b , d e ; a b c , d e f ) \mathcal{B} = (G; ab, de; abc, def) B = ( G ; ab , d e ; ab c , d e f ) is an equal-matching standard marking , then Act ( G ) = { a , b , d , e } \operatorname{Act}(G) = \{a, b, d, e\} Act ( G ) = { a , b , d , e } has the noninterference property.
Proof. Let R R R be an arbitrary nonempty subset of Act ( G ) \operatorname{Act}(G) Act ( G ) . Consider an R R R -join of G G G . Note that a b c abc ab c and d e f def d e f are triangles and Act ( G ) = { a , b , d , e } \operatorname{Act}(G) = \{a, b, d, e\} Act ( G ) = { a , b , d , e } . By the definition of an R R R -join, we have ∣ { a , b , c } ∩ R ∣ ≤ 1 |\{a, b, c\} \cap R| \le1 ∣ { a , b , c } ∩ R ∣ ≤ 1 and ∣ { d , e , f } ∩ R ∣ ≤ 1 |\{d, e, f\} \cap R| \le1 ∣ { d , e , f } ∩ R ∣ ≤ 1 . If ∣ { a , b , c } ∩ R ∣ = 1 |\{a, b, c\} \cap R| = 1 ∣ { a , b , c } ∩ R ∣ = 1 and ∣ { d , e , f } ∩ R ∣ = 1 |\{d, e, f\} \cap R| = 1 ∣ { d , e , f } ∩ R ∣ = 1 , then no lonely edge is nonincident to R R R . This implies that Act ( G ) \operatorname{Act}(G) Act ( G ) satisfies the noninterference property. Otherwise, ∣ R ∩ { a , b , d , e } ∣ = 1 |R \cap\{a, b, d, e\}| = 1 ∣ R ∩ { a , b , d , e } ∣ = 1 . Without loss of generality, assume R = { a } R = \{a\} R = { a } . Then an R R R -join containing d e de d e is exactly a rooted join at the unique root that includes a nonincident lonely edge, which contradicts the fact that the root is in Act ( G ) \operatorname{Act}(G) Act ( G ) .
Let B = ( G ; a b , d e ; a b c , d e f ) \mathcal{B} = (G; ab, de; abc, def) B = ( G ; ab , d e ; ab c , d e f ) be an equal-matching standard marking, and consider the endpoint a a a of the lonely edge a b ab ab . Let p p p be the third neighbor of a a a outside the triangle $abc.
Definition 4.7. In the above situation, let H = G a H=G^{a} H = G a . Update the old lonely edge and the marking by
a b ⟼ a c a p , G a = ( H ; a c a p , d e ; a c a p a b , d e f ) . ab \longmapsto a_{c}a_{p}, \qquad\mathfrak{G}^{a}=(H;a_{c}a_{p},de;a_{c}a_{p}ab,def). ab ⟼ a c a p , G a = ( H ; a c a p , d e ; a c a p ab , d e f ) . This is called endpoint advance at a a a , or Operation E at a a a . The operations at endpoints b , d , e b,d,e b , d , e are defined by the completely symmetric rule.
Figure 5. Operation E.
Lemma 4.8. If G = ( G ; a b , d e ; a b c , d e f ) \mathfrak{G}=(G;ab,de;abc,def) G = ( G ; ab , d e ; ab c , d e f ) is an equal-matching standard marking, then after applying Operation E at any endpoint of a lonely edge, the resulting G a \mathfrak{G}^{a} G a is again an equal-matching standard marking. More precisely, L ( H ) = { a c a p , d e } L(H)=\{a_{c}a_{p},de\} L ( H ) = { a c a p , d e } , Act ( H ) = { a c , a p , d , e } \operatorname{Act}(H)=\{a_{c},a_{p},d,e\} Act ( H ) = { a c , a p , d , e } .
Proof. By Definition 4.5, a ∈ Act ( G ) a\in\operatorname{Act}(G) a ∈ Act ( G ) . This means that Σ G ( a ) = ∅ \Sigma_{G}(a)=\varnothing Σ G ( a ) = ∅ . By Proposition 2.4 , H = G a ∈ U 2 H=G^{a}\in U_{2} H = G a ∈ U 2 and L ( H ) = { λ a ( a b ) , λ a ( d e ) } = { a c a p , d e } L(H)=\{\lambda_{a}(ab),\lambda_{a}(de)\}=\{a_{c}a_{p},de\} L ( H ) = { λ a ( ab ) , λ a ( d e )} = { a c a p , d e } . Recall that M a b = M d e M_{ab}=M_{de} M ab = M d e . By Lemma 4.1, M a c a p = M d e M_{a_{c}a_{p}}=M_{de} M a c a p = M d e .
We now compute the zero-loss vertex set of H H H exactly. Since Act ( G ) = { a , b , d , e } \operatorname{Act}(G)=\{a,b,d,e\} Act ( G ) = { a , b , d , e } and a b ∈ L ( G ) ab\in L(G) ab ∈ L ( G ) , the set appearing in Proposition 4.4 is B a = { b } B_{a}=\{b\} B a = { b } . The zero-loss vertices in the new triangle are given by T a T_{a} T a . The only lonely edge not incident with a a a is d e de d e , and M d e = M a b M_{de}=M_{ab} M d e = M ab . Clearly, a c , a p ∉ M d e ac,a_{p}\notin M_{de} a c , a p ∈ / M d e . By the definition of T a T_{a} T a , T a = { a c , a p } T_{a}=\{a_{c},a_{p}\} T a = { a c , a p } . By Lemma 4.6 , Act ( G ) \operatorname{Act}(G) Act ( G ) is noninterfering, so Proposition 4.4 applies and yields Act ( H ) = ( Act ( G ) ∖ ( { a } ∪ B a ) ) ∪ T a = { a c , a p , d , e } \operatorname{Act}(H)=(\operatorname{Act}(G)\setminus(\{a\}\cup B_{a}))\cup T_{a}=\{a_{c},a_{p},d,e\} Act ( H ) = ( Act ( G ) ∖ ({ a } ∪ B a )) ∪ T a = { a c , a p , d , e } . The new lonely edge a c a p a_{c}a_{p} a c a p lies in the new triangle a b a c a p ab a_{c}a_{p} ab a c a p , while the other lonely edge d e de d e and triangle d e f def d e f are unchanged. Hence all three conditions of Definition 4.5 hold, so G a \mathfrak{G}^{a} G a is an equal-matching standard marking.
Definition 4.9. A marked object G = ( G ; x , v , w , y ; S , ρ ) \mathfrak{G}=(G;x,v,w,y;S,\rho) G = ( G ; x , v , w , y ; S , ρ ) is called an unequal-matching standard marking if the following conditions hold.
(D1) G ∈ U 2 ≠ G\in U_{2}^{\ne} G ∈ U 2 = , and x − v − w − y x-v-w-y x − v − w − y is a path with L ( G ) = { x v , w y } L(G)=\{xv,wy\} L ( G ) = { xv , w y } .
(D2) Act ( G ) = { v , w } ∪ S \operatorname{Act}(G)=\{v,w\}\cup S Act ( G ) = { v , w } ∪ S , S ⊆ V ( G ) ∖ { x , v , w , y } S\subseteq V(G)\setminus\{x,v,w,y\} S ⊆ V ( G ) ∖ { x , v , w , y } , and Act ( G ) \operatorname{Act}(G) Act ( G ) has the noninterference property.
(D3) ρ : S → V ( G ) \rho:S\to V(G) ρ : S → V ( G ) is a mapping satisfying the following. For each u ∈ S u\in S u ∈ S , put p = ρ ( u ) p=\rho(u) p = ρ ( u ) . Then p ∈ N G ( u ) ∖ Act ( G ) p\in N_{G}(u)\setminus\operatorname{Act}(G) p ∈ N G ( u ) ∖ Act ( G ) and, writing N G ( u ) = { p , q , r } N_{G}(u)=\{p,q,r\} N G ( u ) = { p , q , r } , we have { M x v ∩ δ ( u ) , M w y ∩ δ ( u ) } = { { u q } , { u r } } \{M_{xv}\cap\delta(u),M_{wy}\cap\delta(u)\}=\{\{uq\},\{ur\}\} { M xv ∩ δ ( u ) , M w y ∩ δ ( u )} = {{ u q } , { u r }} , where δ ( u ) \delta(u) δ ( u ) denotes the set of edges incident to vertex u u u .
The vertices v , w v,w v , w are called the center vertices, and v w vw v w the center edge in G \mathfrak{G} G . For (D3), we write u → p u\to p u → p , call u u u a tip, and call p p p its direction. The requirement ρ ( u ) ∉ Act ( G ) \rho(u)\notin\operatorname{Act}(G) ρ ( u ) ∈ / Act ( G ) explicitly ensures that an arrow never points to another zero-loss vertex. This eliminates the ambiguity that expanding one tip might simultaneously delete the direction target of another tip.
Let G = ( G ; x , v , w , y ; S , ρ ) \mathfrak{G}=(G;x,v,w,y;S,\rho) G = ( G ; x , v , w , y ; S , ρ ) be an unequal-matching standard marking, with N G ( v ) = { x , w , t } N_{G}(v)=\{x,w,t\} N G ( v ) = { x , w , t } . Expand at the center vertex v v v , labeling the new triangle v x , v w , v t v_{x},v_{w},v_{t} v x , v w , v t . The transferred opposite edge of the old lonely edge x v xv xv is v w v t v_{w}v_{t} v w v t .
Definition 4.10. Let H = G v H = G^v H = G v . Define the new center path, tip set, and direction map by
v t − v w − w − y , S ′ = S ∪ { v x } , ρ ′ ( v x ) = v t , ρ ′ ∣ S = ρ . v_t-v_w-w-y,\qquad S' = S \cup\{v_x\},\qquad\rho'(v_x) = v_t,\qquad\rho'|_S = \rho. v t − v w − w − y , S ′ = S ∪ { v x } , ρ ′ ( v x ) = v t , ρ ′ ∣ S = ρ . This gives the marking G v = ( H ; v t , v w , w , y ; S ′ , ρ ′ ) \mathcal{G}^v = (H; v_t, v_w, w, y; S', \rho') G v = ( H ; v t , v w , w , y ; S ′ , ρ ′ ) . The operation is called center expansion at v v v , or Operation C at v v v . The rule at the right center w w w is completely symmetric.
Figure 6. Operation C: the new centers are v w v_w v w , w w w , and a new tip v x → v t v_x \to v_t v x → v t is created in H H H .
Lemma 4.11. Applying Operation C at either center vertex of an unequal-matching standard marking again yields an unequal-matching standard marking and Act ( H ) = { v w , w } ∪ S ∪ { v x } \operatorname{Act}(H) = \{v_w,w\} \cup S \cup\{v_x\} Act ( H ) = { v w , w } ∪ S ∪ { v x } . Thus all old tips are retained, and exactly one new tip, v x → v t v_x \to v_t v x → v t , is added.
Proof. Note that v ∈ Act ( G ) v \in\operatorname{Act}(G) v ∈ Act ( G ) . By Proposition 2.4 , L ( H ) = { v w v t , w y } L(H) = \{v_wv_t, wy\} L ( H ) = { v w v t , w y } , and Lemma 4.1 gives H ∈ U 2 ≠ H \in\mathcal{U}_2^{\ne} H ∈ U 2 = . Since x ∉ Act ( G ) x \notin\operatorname{Act}(G) x ∈ / Act ( G ) , it follows from the definition of B v B_v B v that B v = ∅ B_v = \varnothing B v = ∅ . Note that the unique lonely edge not incident with v v v is w y wy w y . Because M x v ≠ M w y M_{xv} \ne M_{wy} M xv = M w y , x v ∉ M w y xv \notin M_{wy} xv ∈ / M w y . Clearly, v w ∉ M w y vw \notin M_{wy} v w ∈ / M w y . Therefore, the set T v T_v T v as in Proposition 4.4 is { v x , v w } \{v_x,v_w\} { v x , v w } . It follows that Act ( H ) = ( Act ( G ) ∖ { v } ) ∪ { v x , v w } = { v w , w } ∪ S ∪ { v x } \operatorname{Act}(H) = (\operatorname{Act}(G)\setminus\{v\})\cup\{v_x,v_w\} = \{v_w,w\}\cup S\cup\{v_x\} Act ( H ) = ( Act ( G ) ∖ { v }) ∪ { v x , v w } = { v w , w } ∪ S ∪ { v x } , and this set remains noninterfering. To complete the proof, it suffices to show G v \mathcal{G}^v G v satisfies the third condition in Definition 4.9 .
At the new vertex v x v_x v x , the two unique matchings use v x x v_xx v x x and v x v w v_xv_w v x v w , respectively, while v x v t v_xv_t v x v t belongs to neither; moreover v t ∉ Act ( H ) v_t \notin\operatorname{Act}(H) v t ∈ / Act ( H ) . Thus v x → v t v_x \to v_t v x → v t satisfies the conditions. Finally consider an old tip u → ρ ( u ) u \to\rho(u) u → ρ ( u ) . Since ρ ( u ) ∉ Act ( G ) \rho(u) \notin\operatorname{Act}(G) ρ ( u ) ∈ / Act ( G ) but v ∈ Act ( G ) v \in\operatorname{Act}(G) v ∈ Act ( G ) , no old arrow can point to v v v . If u u u is not adjacent to v v v , its local matching pattern is unchanged; if u u u is adjacent to v v v , the old edge u v uv uv is simply replaced by the corresponding external edge u v u uv_u u v u , and the relation describing which nondirectional edge is used at u u u by each matching is unchanged. Proposition 4.4 also shows that every old non-zero-loss vertex remains non-zero-loss, so every old arrow target remains outside the zero-loss vertex set. □ \square □
Let G = ( G ; x , v , w , y ; S , ρ ) \mathcal{G} = (G; x,v,w,y; S,\rho) G = ( G ; x , v , w , y ; S , ρ ) be an unequal-matching standard marking. Choose a tip u ∈ S u \in S u ∈ S , put p = ρ ( u ) p = \rho(u) p = ρ ( u ) , and write N G ( u ) = { p , q , r } N_G(u) = \{p,q,r\} N G ( u ) = { p , q , r } . After exchanging the names of q , r q,r q , r if necessary, assume that M x v M_{xv} M xv uses u q uq u q at u u u and M w y M_{wy} M w y uses u r ur u r . Expand at u u u to the new triangle u p u q u r u_pu_qu_r u p u q u r .
Definition 4.12. Let H = G u H = G^u H = G u and put S ′ = ( S ∖ { u } ) ∪ { u p } S' = (S\setminus\{u\})\cup\{u_p\} S ′ = ( S ∖ { u }) ∪ { u p } . Define ρ ′ ( u p ) = p \rho'(u_p) = p ρ ′ ( u p ) = p , ρ ′ ∣ S ∖ { u } = ρ \rho'|_{S\setminus\{u\}} = \rho ρ ′ ∣ S ∖ { u } = ρ . The center path remains x − v − w − y x-v-w-y x − v − w − y . The resulting marking G u = ( H ; x , v , w , y ; S ′ , ρ ′ ) \mathcal{G}^u = (H; x,v,w,y; S',\rho') G u = ( H ; x , v , w , y ; S ′ , ρ ′ ) is called tip extension , or Operation T.
Figure 7. Operation T. The old tip u → p u \to p u → p is replaced by the new tip u p → p u_p \to p u p → p .
Lemma 4.13. Applying Operation T T T at any tip of an unequal-matching standard marking again yields an unequal-matching standard marking, and Act ( H ) = { v , w } ∪ ( S ∖ { u } ) ∪ { u p } \operatorname{Act}(H)=\{v,w\}\cup(S\setminus\{u\})\cup\{u_p\} Act ( H ) = { v , w } ∪ ( S ∖ { u }) ∪ { u p } . The center vertices and all other tips remain unchanged, and the number of expandable vertices is unchanged.
Proof. By Definition 4.9 , the tip u u u does not belong to the four vertices of the center path, so neither lonely edge is incident with u u u , and B u = ∅ B_u=\varnothing B u = ∅ . By the tip condition, u p up u p belongs to neither M x v M_{xv} M xv nor M w y M_{wy} M w y , while u q uq u q and u r ur u r are used by the two matchings, respectively. Hence by Lemma 4.2 , u p u_p u p is zero-loss expandable in the new triangle, that is, T u = { u p } T_u=\{u_p\} T u = { u p } .
Proposition 4.4 gives Act ( H ) = ( Act ( G ) ∖ { u } ) ∪ { u p } = { v , w } ∪ ( S ∖ { u } ) ∪ { u p } \operatorname{Act}(H)=(\operatorname{Act}(G)\setminus\{u\})\cup\{u_p\}=\{v,w\}\cup(S\setminus\{u\})\cup\{u_p\} Act ( H ) = ( Act ( G ) ∖ { u }) ∪ { u p } = { v , w } ∪ ( S ∖ { u }) ∪ { u p } , and guarantees that this set remains noninterfering. By Proposition 2.4 and Lemma 4.1, H ∈ U 2 − H\in\mathcal{U}_2^{-} H ∈ U 2 − , and the two lonely edges and the center path are unchanged.
After natural lifting, M x v M_{xv} M xv uses u q q u_q q u q q and u p u r u_p u_r u p u r in the new triangle, while M w y M_{wy} M w y uses u r r u_r r u r r and u p u q u_p u_q u p u q . Thus at u p u_p u p the two matchings use two different triangle edges, and the external edge u p p u_p p u p p belongs to neither; the new arrow is therefore u p → p u_p\to p u p → p . Since p ∉ Act ( G ) p\notin\operatorname{Act}(G) p ∈ / Act ( G ) originally, the formula above shows that p ∉ Act ( H ) p\notin\operatorname{Act}(H) p ∈ / Act ( H ) as well.
For any other old tip z → ρ ( z ) z\to\rho(z) z → ρ ( z ) , arrow targets lie outside Act ( G ) \operatorname{Act}(G) Act ( G ) , so ρ ( z ) ≠ u \rho(z)\ne u ρ ( z ) = u . Hence expanding u u u does not delete the target of any other arrow. If z z z is adjacent to u u u , the corresponding nondirectional edge is merely replaced by an external edge and the matching-use pattern is preserved; otherwise the local structure is unchanged. The same argument applies at the center vertices: if u u u is the third neighbor of a center, the relevant old matching edge is simply rerouted to the corresponding new vertex, so the local matching pattern at each center is preserved. Hence all standard-marking conditions are preserved.
Corollary 4.14. In an equal-matching standard marking, the zero-loss vertices are always exactly the four endpoints of the two lonely edges, so every step has exactly four possible Operation E E E choices.
In an unequal-matching standard marking with k k k tips, the zero-loss vertices are exactly the two center vertices together with those k k k tips. Operation C C C at either center increases the number of tips by 1 1 1 , whereas the other k k k Operation T T T choices merely extend existing tips and leave the number of tips unchanged.
Remark 4.15. Up to this point we have proved only the following conditional statement: once a graph carries an equal-matching or unequal-matching standard marking, the allowed local operations produce another standard marking of the same type. We have not yet proved that the lonely edges of every G ∈ U 2 − G\in\mathcal{U}_2^{-} G ∈ U 2 − lie in triangles, nor that every G ∈ U 2 − G\in\mathcal{U}_2^{-} G ∈ U 2 − has a center path and tips. These general conclusions will be derived in § 5.1 from the primitive-kernel base cases and kernel-reduction induction.
Standard-marking base cases for the primitive kernels
In this subsection we do not assume that a general graph in U 2 \mathcal{U}_2 U 2 already has the standard structure. Instead, we verify one by one that every primitive kernel admits at least one standard marking in the sense of Subsection 4.2. These kernels will serve as the induction bases in Subsection 4.4. In the figures, dashed edges are lonely edges, double circles indicate center vertices, the tail of an arrow is a tip, and the head of the arrow is its direction.
Using the integer labels from Subsection 3.3, all three kernels are of unequal-matching type. Their center paths and tips are
D 0 : 10 − 1 − 8 − 4 , 0 → 5 , 2 → 3 , 9 → 4 , 11 → 10 D_0:\quad10-1-8-4,\qquad0\to5,\quad2\to3,\quad9\to4,\quad11\to10 D 0 : 10 − 1 − 8 − 4 , 0 → 5 , 2 → 3 , 9 → 4 , 11 → 10
D 1 D_1 D 1 : 3 − 1 − 8 − 4 3-1-8-4 3 − 1 − 8 − 4 , \quad 2 → 3 2 \to3 2 → 3 , \quad 9 → 4 9 \to4 9 → 4 , \quad 13 → 5 13 \to5 13 → 5 ;
D 2 D_2 D 2 : 1 − 3 − 6 − 7 1-3-6-7 1 − 3 − 6 − 7 , \quad 2 → 1 2 \to1 2 → 1 , \quad 9 → 5 9 \to5 9 → 5 , \quad 12 → 7 12 \to7 12 → 7 .
In each row, the first and last edges of the four-vertex path are the lonely edges and the two internal vertices are the centers.
Use the natural labels U = u 1 u 2 u 3 U=u_1u_2u_3 U = u 1 u 2 u 3 and X j = x 1 j x 2 j x 3 j X^j=x_1^jx_2^jx_3^j X j = x 1 j x 2 j x 3 j . Standard markings for the three equal-matching kernels are listed below. The column “containing triangles” explicitly records the structural data from Definition 4.5 that cannot be omitted in advance.
Table 1 (PDF p. 18).
Standard markings for the four unequal-matching kernels are as follows.
Table 2 (PDF p. 18).
Lemma 4.16. For the ten finite primitive kernels listed in Figure 8 and the two tables above, the following all hold:
(a) the listed lonely edges and matching types are correct;
(b) the listed vertices are exactly all zero-loss expansion vertices;
(c) the three equal-matching graphs satisfy Definition 4.5;
(d) the seven unequal-matching graphs satisfy Definition 4.9 ; in particular, the matching direction at every tip, inactivity of every arrow target, and noninterference of the zero-loss vertex set all hold.
Figure 8. One unequal-matching standard marking for three non-extended-prism kernels.
Proof. For each of the ten graphs, we enumerate its perfect matchings and count the occurrences of each edge to determine its lonely edges and their unique perfect matchings. Comparing these two matchings determines the matching type. We compute the complete zero-loss vertex set using Lemma 2.3 , and check the listed triangles, center paths, and tip directions directly. For each nonempty subset R R R of the proposed zero-loss vertex set and each lonely edge e e e nonincident with R R R , we select all edges incident with R R R together with e e e . If a non-root has degree greater than 1, no such R R R -join exists; otherwise, the remaining uncovered vertices must have a perfect matching. Exhaustive matching enumeration excludes this possibility in every case. These checks establish all four assertions; the computations and certificates are provided in [8 ] .
For the next two lemmas, let G = P ( 12 r t ) G=P(12^{r}t) G = P ( 1 2 r t ) , where r ≥ 2 r \ge2 r ≥ 2 and t ∈ { 1 , 3 } t \in\{1,3\} t ∈ { 1 , 3 } , and put q = 4 − t q=4-t q = 4 − t . To specify the alternating edge sets, including their boundary edges, write
e 0 1 = u 1 x 1 1 , e 0 3 = x 3 0 x 3 1 , e r t = x t r x t r + 2 , e r q = x q r x q r + 1 , e i j = x j i x j i + 1 ( 1 ≤ i < r , j ∈ { 1 , 3 } ) . e_{0}^{1}=u_{1}x_{1}^{1},\quad e_{0}^{3}=x_{3}^{0}x_{3}^{1},\quad e_{r}^{t}=x_{t}^{r}x_{t}^{r+2},\quad e_{r}^{q}=x_{q}^{r}x_{q}^{r+1},\quad e_{i}^{j}=x_{j}^{i}x_{j}^{i+1}\ (1\le i<r,\ j\in\{1,3\}). e 0 1 = u 1 x 1 1 , e 0 3 = x 3 0 x 3 1 , e r t = x t r x t r + 2 , e r q = x q r x q r + 1 , e i j = x j i x j i + 1 ( 1 ≤ i < r , j ∈ { 1 , 3 }) .
The pair { e i 1 , e i 3 } \{e_{i}^{1},e_{i}^{3}\} { e i 1 , e i 3 } is the pair of rail edges at cut i i i . A rail-edge selection is called alternating if it selects one edge at each consecutive cut and switches rails at each step. Put η i = 1 \eta_i=1 η i = 1 for even i i i and η i = 3 \eta_i=3 η i = 3 for odd i i i , and define
A a , b = { e i η i : a ≤ i ≤ b } , B a , b = { e i 4 − η i : a ≤ i ≤ b } , R = { x 1 k x 3 k : 1 ≤ k ≤ r } . A_{a,b}=\{e_{i}^{\eta_i}:a\le i\le b\},\qquad B_{a,b}=\{e_{i}^{4-\eta_i}:a\le i\le b\},\qquad R=\{x_{1}^{k}x_{3}^{k}:1\le k\le r\}. A a , b = { e i η i : a ≤ i ≤ b } , B a , b = { e i 4 − η i : a ≤ i ≤ b } , R = { x 1 k x 3 k : 1 ≤ k ≤ r } .
Here 0 ≤ a ≤ b ≤ r 0\le a\le b\le r 0 ≤ a ≤ b ≤ r , and an interval with a > b a>b a > b denotes the empty set. Thus R R R contains only the internal rungs. If neither vertex of an internal rung is a root and exactly one rail edge is selected at one adjacent cut, the degree requirements exclude the rung and force the other rail at the next cut. Consequently, alternating selections propagate through every segment containing no roots.
Let
s k = { x 3 k , k is odd , x 1 k , k is even , s ˉ k = { x 1 k , k is odd , x 3 k , k is even . (9) s_k=\begin{cases}
x_{3}^{k},& k\text{ is odd},\\
x_{1}^{k},& k\text{ is even},
\end{cases}
\qquad
\bar{s}_k=\begin{cases}
x_{1}^{k},& k\text{ is odd},\\
x_{3}^{k},& k\text{ is even}.
\end{cases} \tag*{(9)} s k = { x 3 k , x 1 k , k is odd , k is even , s ˉ k = { x 1 k , x 3 k , k is odd , k is even . (9)
Here 1 ≤ k ≤ r 1\le k\le r 1 ≤ k ≤ r . Clearly, { s k , s ˉ k } = { x 1 k , x 3 k } \{s_k,\bar{s}_k\}=\{x_{1}^{k},x_{3}^{k}\} { s k , s ˉ k } = { x 1 k , x 3 k } .
Lemma 4.17. Let r ≥ 2 r\ge2 r ≥ 2 and t ∈ { 1 , 3 } t\in\{1,3\} t ∈ { 1 , 3 } . If t = 1 t=1 t = 1 and r r r is even, or t = 3 t=3 t = 3 and r r r is odd, then
L ( P ( 12 r t ) ) = { u 1 u 3 , x 1 r + 2 x 3 r + 2 } , M u 1 u 3 = M x 1 r + 2 x 3 r + 2 , Act ( P ( 12 r t ) ) = { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } . L(P(12^{r}t))=\{u_{1}u_{3},x_{1}^{r+2}x_{3}^{r+2}\},\quad M_{u_{1}u_{3}}=M_{x_{1}^{r+2}x_{3}^{r+2}},\quad\operatorname{Act}(P(12^{r}t))=\{u_{1},u_{3},x_{1}^{r+2},x_{3}^{r+2}\}. L ( P ( 1 2 r t )) = { u 1 u 3 , x 1 r + 2 x 3 r + 2 } , M u 1 u 3 = M x 1 r + 2 x 3 r + 2 , Act ( P ( 1 2 r t )) = { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } . Proof. By Lemma 3.9 and Corollary 3.10, we have L ( P ( 12 r t ) ) = { u 1 u 3 , x 1 r + 2 x 3 r + 2 } L(P(12^{r}t))=\{u_{1}u_{3},x_{1}^{r+2}x_{3}^{r+2}\} L ( P ( 1 2 r t )) = { u 1 u 3 , x 1 r + 2 x 3 r + 2 } and M u 1 u 3 = M x 1 r + 2 x 3 r + 2 M_{u_{1}u_{3}}=M_{x_{1}^{r+2}x_{3}^{r+2}} M u 1 u 3 = M x 1 r + 2 x 3 r + 2 . To complete the proof, it suffices to show that
Act ( P ( 12 r t ) ) = { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } . \operatorname{Act}(P(12^{r}t))=\{u_{1},u_{3},x_{1}^{r+2},x_{3}^{r+2}\}. Act ( P ( 1 2 r t )) = { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } . First, we show that { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } ⊆ Act ( G ) \{u_{1},u_{3},x_{1}^{r+2},x_{3}^{r+2}\}\subseteq\operatorname{Act}(G) { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } ⊆ Act ( G ) by contradiction. Suppose that there exists a y y y -rooted join J y J_y J y containing a lonely edge not incident with y y y , where y ∈ { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } y\in\{u_{1},u_{3},x_{1}^{r+2},x_{3}^{r+2}\} y ∈ { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } .
Since u 3 u_{3} u 3 is the root of J u 3 J_{u_{3}} J u 3 , { u 1 u 3 , u 2 u 3 , u 3 x 3 0 } ⊆ E ( J u 3 ) \{u_{1}u_{3},u_{2}u_{3},u_{3}x_{3}^{0}\}\subseteq E(J_{u_{3}}) { u 1 u 3 , u 2 u 3 , u 3 x 3 0 } ⊆ E ( J u 3 ) . The degree requirement at x 2 0 x_{2}^{0} x 2 0 then forces x 2 0 x 2 r + 1 ∈ E ( J u 3 ) x_{2}^{0}x_{2}^{r+1}\in E(J_{u_{3}}) x 2 0 x 2 r + 1 ∈ E ( J u 3 ) . On the other hand, the nonincident lonely edge in J u 3 J_{u_{3}} J u 3 must be x 1 r + 2 x 3 r + 2 x_{1}^{r+2}x_{3}^{r+2} x 1 r + 2 x 3 r + 2 , which forces x 2 r + 1 x 2 r + 2 ∈ E ( J u 3 ) x_{2}^{r+1}x_{2}^{r+2}\in E(J_{u_{3}}) x 2 r + 1 x 2 r + 2 ∈ E ( J u 3 ) . Thus the non-root x 2 r + 1 x_{2}^{r+1} x 2 r + 1 has degree at least 2, a contradiction.
For J u 1 J_{u_{1}} J u 1 , the root forces u 1 u 2 , u 1 u 3 , u 1 x 1 1 ∈ E ( J u 1 ) u_{1}u_{2},u_{1}u_{3},u_{1}x_{1}^{1}\in E(J_{u_{1}}) u 1 u 2 , u 1 u 3 , u 1 x 1 1 ∈ E ( J u 1 ) . The nonincident lonely edge x 1 r + 2 x 3 r + 2 x_{1}^{r+2}x_{3}^{r+2} x 1 r + 2 x 3 r + 2 forces x 1 r + 1 x 3 r + 2 x_{1}^{r+1}x_{3}^{r+2} x 1 r + 1 x 3 r + 2 and excludes x 2 r + 1 x 2 r + 2 x_{2}^{r+1}x_{2}^{r+2} x 2 r + 1 x 2 r + 2 . Hence x 2 r x 3 r x_{2}^{r}x_{3}^{r} x 2 r x 3 r is selected, and x 3 r x 3 r + 1 x_{3}^{r}x_{3}^{r+1} x 3 r x 3 r + 1 is excluded. At the right end, the non-root x q r x_{q}^{r} x q r can therefore only be covered by e r q e_{r}^{q} e r q . However, the entrance edge e 0 1 = u 1 x 1 1 e_{0}^{1}=u_{1}x_{1}^{1} e 0 1 = u 1 x 1 1 forces the alternating selection A 0 , r A_{0,r} A 0 , r through the root-free internal rungs. In the present parity cases η r = t \eta_r=t η r = t , so the selected exit is e r t e_{r}^{t} e r t , not e r q e_{r}^{q} e r q . This is a contradiction.
Now let the root be x q r + 2 x_{q}^{r+2} x q r + 2 and suppose that the join contains u 1 u 3 u_{1}u_{3} u 1 u 3 . The left end forces u 2 x 2 0 , x 3 0 x 3 1 u_{2}x_{2}^{0},x_{3}^{0}x_{3}^{1} u 2 x 2 0 , x 3 0 x 3 1 and excludes x 2 0 x 2 r + 1 x_{2}^{0}x_{2}^{r+1} x 2 0 x 2 r + 1 . The three edges at the root cover x q r + 1 , x 2 r + 2 , x t r + 2 x_{q}^{r+1},x_{2}^{r+2},x_{t}^{r+2} x q r + 1 , x 2 r + 2 , x t r + 2 . Consequently, none of the three neighbors of x q r + 1 x_{q}^{r+1} x q r + 1 can be joined to it, a contradiction. Finally, if
the root is x r + 2 r + 2 x_{r+2}^{r+2} x r + 2 r + 2 , the same left-end forcing excludes x 2 0 x 2 r + 1 x_2^0x_2^{r+1} x 2 0 x 2 r + 1 and gives entrance e 0 3 e_0^3 e 0 3 . The root forces e r q e_r^q e r q and its two triangle edges, after which x 2 r + 1 x q r + 1 x_2^{r+1}x_q^{r+1} x 2 r + 1 x q r + 1 is forced and e r q e_r^q e r q is excluded. But the entrance e 0 3 e_0^3 e 0 3 propagates as B 0 , r B_{0,r} B 0 , r , and, since η r = t \eta_r=t η r = t , exits on rail q q q , again a contradiction. Thus all four claimed vertices are zero-loss expandable.
To prove that no other vertex is zero-loss expandable, we construct a y y y -rooted join containing a lonely edge not incident with y y y for every y ∈ V ( G ) ∖ { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } y \in V(G) \setminus\{u_1,u_3,x_1^{r+2},x_3^{r+2}\} y ∈ V ( G ) ∖ { u 1 , u 3 , x 1 r + 2 , x 3 r + 2 } . In each row below, the edge set of the join is the union of δ ( y ) \delta(y) δ ( y ) , the listed lonely edge, and the edge sets in the last two columns. Repeated edges are included only once, and 1 ≤ k ≤ r 1 \le k \le r 1 ≤ k ≤ r .
Table 4.
For an internal root s k s_k s k or s ˉ k \bar{s}_k s ˉ k , the selections on cuts k − 1 k-1 k − 1 and k k k lie on the root’s rail, and its rung is supplied by δ ( y ) \delta(y) δ ( y ) . The root therefore has degree 3, while the opposite vertex has degree 1. At every other internal rung, the two adjacent selected rail edges lie on different rails, so both vertices have degree 1. For a row using R \mathcal{R} R , each internal vertex is covered by its rung. The displayed boundary edges and δ ( y ) \delta(y) δ ( y ) give degree 1 at every remaining non-root vertex. Thus every row defines the required join. The rows cover all 2 r + 6 2r+6 2 r + 6 vertices outside the claimed zero-loss set, completing the proof.
Lemma 4.18. Let r ≥ 2 r \ge2 r ≥ 2 and t ∈ { 1 , 3 } t \in\{1,3\} t ∈ { 1 , 3 } . The extended prism P ( 12 r t ) P(12rt) P ( 12 r t ) admits an unequal-matching standard marking when t = 1 t=1 t = 1 and r r r is odd, or t = 3 t=3 t = 3 and r r r is even.
Proof. We prove this result by showing that G = ( G ; x 3 0 , x 2 0 , x 2 r + 1 , x q r + 1 ; S , ρ ) \mathcal{G}=(G;x_3^0,x_2^0,x_2^{r+1},x_q^{r+1};S,\rho) G = ( G ; x 3 0 , x 2 0 , x 2 r + 1 , x q r + 1 ; S , ρ ) is an unequal-matching standard marking of G = P ( 12 r t ) G=P(12r^t) G = P ( 12 r t ) , where S = { u 3 , x q r + 2 , s 1 , ⋯ , s r } S=\{u_3,x_q^{r+2},s_1,\cdots,s_r\} S = { u 3 , x q r + 2 , s 1 , ⋯ , s r } and
ρ ( u 3 ) = x 3 0 , ρ ( x q r + 2 ) = x q r + 1 , ρ ( s k ) = s ˉ k ( 1 ≤ k ≤ r ) . \rho(u_3)=x_3^0,\qquad\rho(x_q^{r+2})=x_q^{r+1},\qquad\rho(s_k)=\bar{s}_k\quad(1\le k\le r). ρ ( u 3 ) = x 3 0 , ρ ( x q r + 2 ) = x q r + 1 , ρ ( s k ) = s ˉ k ( 1 ≤ k ≤ r ) .
The lonely edges and the distinct-matching type follow from Lemma 3.9 and Corollary 3.10; explicitly, L ( G ) = { x 2 0 x 3 0 , x q r + 1 x q r + 1 } L(G)=\{x_2^0x_3^0,x_q^{r+1}x_q^{r+1}\} L ( G ) = { x 2 0 x 3 0 , x q r + 1 x q r + 1 } . Let A = { x 2 0 , x 2 r + 1 , u 3 , x q r + 2 , s 1 , … , s r } A=\{x_2^0,x_2^{r+1},u_3,x_q^{r+2},s_1,\ldots,s_r\} A = { x 2 0 , x 2 r + 1 , u 3 , x q r + 2 , s 1 , … , s r } .
Claim: A A A is noninterfering.
Proof of Claim. Suppose, to the contrary, that there are a nonempty R ⊆ A R\subseteq A R ⊆ A , an R R R -join J J J , and an edge e ∈ L ( G ) ∩ E ( J ) e\in L(G)\cap E(J) e ∈ L ( G ) ∩ E ( J ) with V ( e ) ∩ R = ∅ V(e)\cap R=\varnothing V ( e ) ∩ R = ∅ .
Suppose e = x 2 0 x 3 0 e=x_2^0x_3^0 e = x 2 0 x 3 0 . Neither endpoint is a root, so x 2 0 x 2 r + 1 x_2^0x_2^{r+1} x 2 0 x 2 r + 1 , u 2 x 2 0 u_2x_2^0 u 2 x 2 0 , u 3 x 3 0 u_3x_3^0 u 3 x 3 0 , and x 3 0 x 3 1 x_3^0x_3^1 x 3 0 x 3 1 are excluded from J J J . In particular, u 3 , x 2 r + 1 ∉ R u_3,x_2^{r+1}\notin R u 3 , x 2 r + 1 ∈ / R . The degree requirements at u 1 , u 2 , u 3 u_1,u_2,u_3 u 1 , u 2 , u 3 then force u 2 u 3 , u 1 x 1 r + 1 ∈ E ( J ) u_2u_3,u_1x_1^{r+1}\in E(J) u 2 u 3 , u 1 x 1 r + 1 ∈ E ( J ) . If x q r + 2 x_q^{r+2} x q r + 2 were a root, its three incident edges would cover x q r + 1 , x 2 r + 2 , x t 0 x_q^{r+1},x_2^{r+2},x_t^0 x q r + 1 , x 2 r + 2 , x t 0 . Since x 2 0 x 2 r + 1 x_2^0x_2^{r+1} x 2 0 x 2 r + 1 is absent, the non-root x 2 r + 1 x_2^{r+1} x 2 r + 1 would have no available neighbor. Thus x q r + 2 ∉ R x_q^{r+2}\notin R x q r + 2 ∈ / R , and R ⊆ { s 1 , … , s r } R\subseteq\{s_1,\ldots,s_r\} R ⊆ { s 1 , … , s r } .
Let s j s_j s j be the root with smallest index. Before cell j j j , all cells contain no roots, so the entrance e 0 1 e_0^1 e 0 1 forces A 0 , j − 1 A_{0,j-1} A 0 , j − 1 . The selected edge at cut j − 1 j-1 j − 1 lies on rail η j − 1 = 4 − η j \eta_{j-1}=4-\eta_j η j − 1 = 4 − η j , whereas the root s j = x j r s_j=x_j^{r} s j = x j r requires the edge on rail η j \eta_j η j at that cut. This is a contradiction.
Suppose e = x 2 r + 1 x q r + 1 e=x_2^{r+1}x_q^{r+1} e = x 2 r + 1 x q r + 1 . Neither endpoint is a root. Hence x 2 0 x 2 r + 1 x_2^0x_2^{r+1} x 2 0 x 2 r + 1 , x 2 r + 1 x 2 r + 2 x_2^{r+1}x_2^{r+2} x 2 r + 1 x 2 r + 2 , e r q e_r^q e r q , and x q r + 1 x q r + 2 x_q^{r+1}x_q^{r+2} x q r + 1 x q r + 2 are excluded from J J J . It follows that x 2 0 , x q r + 2 ∉ R x_2^0,x_q^{r+2}\notin R x 2 0 , x q r + 2 ∈ / R . If u 3 u_3 u 3 were a root, its
three incident edges would cover u 1 u_1 u 1 , u 2 u_2 u 2 , x 3 0 x_3^0 x 3 0 , leaving x 2 0 x_2^0 x 2 0 with no available neighbor. Thus u 3 ∉ R u_3 \notin R u 3 ∈ / R , and again R ⊆ { s 1 , … , s r } R \subseteq\{s_1,\ldots,s_r\} R ⊆ { s 1 , … , s r } . The root-free right end forces x q r + 2 x 2 r + 2 x_q^{r+2}x_2^{r+2} x q r + 2 x 2 r + 2 and e r t e_r^t e r t . Let s j s_j s j be the root with largest index. In the present parity cases, t = 4 − η r t=4-\eta_r t = 4 − η r . Propagating backward from e r t e_r^t e r t through the cells with indices greater than j j j selects the edge on rail 4 − η j 4-\eta_j 4 − η j at cut j j j . But the root s j = x η j j s_j=x_{\eta_j}^j s j = x η j j requires the edge on rail η j \eta_j η j at that cut, a contradiction.
Both cases are impossible, proving the claim.
Taking singleton root sets in the noninterference property gives A ⊆ Act ( G ) A\subseteq\operatorname{Act}(G) A ⊆ Act ( G ) . To prove equality, we construct the joins listed below. As in the preceding proof, each join consists of δ ( y ) \delta(y) δ ( y ) , the listed lonely edge, and the last two columns; repeated edges are included only once, and 1 ≤ k ≤ r 1\leq k\leq r 1 ≤ k ≤ r .
Table 1 (PDF p. 21).
The degree verification is the same as in the preceding table: alternating selections cover each root-free internal cell once, and at cell k k k the change from A A A to B B B gives both rail edges at s ˉ k \bar{s}_k s ˉ k , whose rung is supplied by δ ( s ˉ k ) \delta(\bar{s}_k) δ ( s ˉ k ) . The boundary edges complete the required degrees. Thus every row gives a join containing the stated nonincident lonely edge. The rows cover all r + 6 r+6 r + 6 vertices outside A A A , so A = Act ( G ) A=\operatorname{Act}(G) A = Act ( G ) .
Finally, the two unique perfect matchings can be written as
M x 2 0 x 3 0 = { x 2 0 x 3 0 , u 2 u 3 , x q r + 1 x q r + 2 , x 2 r + 1 x 3 r + 2 } ∪ A 0 , r . M_{x_2^0x_3^0}=\{x_2^0x_3^0,u_2u_3,x_q^{r+1}x_q^{r+2},x_2^{r+1}x_3^{r+2}\}\cup A_{0,r}. M x 2 0 x 3 0 = { x 2 0 x 3 0 , u 2 u 3 , x q r + 1 x q r + 2 , x 2 r + 1 x 3 r + 2 } ∪ A 0 , r .
M x 2 r + 1 x q r + 1 = { u 1 u 3 , u 2 x 2 0 , x q r + 1 x q r + 1 , x 2 r + 2 x q r + 2 } ∪ B 0 , r . M_{x_2^{r+1}x_q^{r+1}}=\{u_1u_3,u_2x_2^0,x_q^{r+1}x_q^{r+1},x_2^{r+2}x_q^{r+2}\}\cup B_{0,r}. M x 2 r + 1 x q r + 1 = { u 1 u 3 , u 2 x 2 0 , x q r + 1 x q r + 1 , x 2 r + 2 x q r + 2 } ∪ B 0 , r .
At each s k s_k s k , these matchings use the two different rail edges and neither uses the rung s k s ˉ k s_k\bar{s}_k s k s ˉ k . At u 3 u_3 u 3 , they use u 2 u 3 u_2u_3 u 2 u 3 and u 1 u 3 u_1u_3 u 1 u 3 , respectively; at x q r + 2 x_q^{r+2} x q r + 2 , they use its two different triangle edges. Thus every indicated tip has the required matching pattern. All arrow targets lie outside A = Act ( G ) A=\operatorname{Act}(G) A = Act ( G ) . Together with the claim and the center path x 3 0 − x 2 0 − x 2 r + 1 − x q r + 1 x_3^0-x_2^0-x_2^{r+1}-x_q^{r+1} x 3 0 − x 2 0 − x 2 r + 1 − x q r + 1 , this verifies all conditions of Definition 4.9 .
Theorem 4.19. Every primitive U 2 U_2 U 2 kernel admits at least one standard marking.
Proof. The ten finite primitive kernels are covered by Lemma 4.16 , and the four parity cases of the two infinite kernel families are covered by Lemmas 4.17 and 4.18 .
Complete construction theorem
Only now do we deduce the concrete structure of an arbitrary graph in U 2 U_2 U 2 from the facts that primitive kernels admit standard markings and that standard markings are closed under the three operations. In particular, the fact that the lonely edges of an equal-matching graph lie in triangles is proved here rather than assumed in § 4.2 .
Theorem 4.20. The following hold.
Every G ∈ U 2 = G\in\mathcal{U}_2^= G ∈ U 2 = admits at least one equal-matching standard marking.
(ii) Every G ∈ U 2 ≠ G \in U_2^{\ne} G ∈ U 2 = admits at least one unequal-matching standard marking.
Proof. Take any G ∈ U 2 G \in U_2 G ∈ U 2 . By Proposition 2.9, there is a primitive kernel C C C and a zero-loss expansion sequence
C = G 0 , G 1 , ⋯ , G s = G , G i + 1 = G v i i , v i ∈ Act ( G i ) . C = G_0, G_1, \cdots, G_s = G,\qquad G_{i+1} = G_{v_i}^{i},\qquad v_i \in\operatorname{Act}(G_i). C = G 0 , G 1 , ⋯ , G s = G , G i + 1 = G v i i , v i ∈ Act ( G i ) .
By Lemma 4.1, the matching type is preserved at every zero-loss expansion. Thus if G ∈ U 2 = G \in U_2^= G ∈ U 2 = , then every G i G_i G i and the primitive kernel C C C are of equal-matching type; if G ∈ U 2 ≠ G \in U_2^{\ne} G ∈ U 2 = , the entire sequence is of unequal-matching type. By Theorem 4.19 , G 0 = C G_0 = C G 0 = C has a standard marking of the corresponding type.
We now induct on i i i , assuming that G i G_i G i carries the marking propagated along the sequence. If G i G_i G i is of equal-matching type, the definition of the standard marking gives
Act ( G i ) = { the four endpoints of the two lonely edges } . \operatorname{Act}(G_i) = \{\text{the four endpoints of the two lonely edges}\}. Act ( G i ) = { the four endpoints of the two lonely edges } .
Since v i ∈ Act ( G i ) v_i \in\operatorname{Act}(G_i) v i ∈ Act ( G i ) , the current step can only be Operation E at an endpoint of a lonely edge. Lemma 4.8 then gives an equal-matching standard marking on G i + 1 G_{i+1} G i + 1 .
If G i G_i G i is of unequal-matching type, the definition gives
Act ( G i ) = { the two center vertices } ∪ { all tips } . \operatorname{Act}(G_i) = \{\text{the two center vertices}\} \cup\{\text{all tips}\}. Act ( G i ) = { the two center vertices } ∪ { all tips } .
If v i v_i v i is a center vertex, the step is necessarily Operation C, and Lemma 4.11 supplies the standard marking on G i + 1 G_{i+1} G i + 1 . If v i v_i v i is a tip, the step is necessarily Operation T, and Lemma 4.13 gives the next marking. These two cases exhaust all zero-loss vertices.
Induction to i = s i=s i = s yields a standard marking on G G G and simultaneously proves that every step of the given zero-loss sequence is identified exactly by one of the three operations. □
Let C 2 = E 2 ∪ { D 0 , D 1 , D 2 } \mathcal{C}_2 = \mathcal{E}_2 \cup\{D_0,D_1,D_2\} C 2 = E 2 ∪ { D 0 , D 1 , D 2 } be the set of primitive U 2 U_2 U 2 kernels, and put
C 2 = = C 2 ∩ U 2 = , C 2 ≠ = C 2 ∩ U 2 ≠ . \mathcal{C}_2^= = \mathcal{C}_2 \cap U_2^=,\qquad\mathcal{C}_2^{\ne} = \mathcal{C}_2 \cap U_2^{\ne}. C 2 = = C 2 ∩ U 2 = , C 2 = = C 2 ∩ U 2 = .
Theorem 4.21. For every Klee graph G G G , the following statements hold.
(i) G ∈ U 2 = G \in U_2^= G ∈ U 2 = if and only if G G G can be obtained from some C ∈ C 2 = C \in\mathcal{C}_2^= C ∈ C 2 = by finitely many applications of endpoint advance at a lonely-edge endpoint;
(ii) G ∈ U 2 ≠ G \in U_2^{\ne} G ∈ U 2 = if and only if G G G can be obtained from some C ∈ C 2 ≠ C \in\mathcal{C}_2^{\ne} C ∈ C 2 = by finitely many applications of center expansion and tip extension;
(iii) U 2 = U 2 = ∪ U 2 ≠ U_2 = U_2^= \cup U_2^{\ne} U 2 = U 2 = ∪ U 2 = is exactly the union of the two classes produced by these constructions.
At every step, the three vertices of the new triangle, the two lonely edges, the center vertices, and the tip directions are updated uniquely according to the labeling rules in § 4.2 .
Proof. First, every graph constructed by the three operations belongs to the corresponding class of U 2 U_2 U 2 . Every seed kernel belongs to U 2 U_2 U 2 and, by Theorem 4.19 , carries a standard marking. The root of each of Operations E, C, T belongs to the current zero-loss vertex set, so every step satisfies Σ G ( v ) = ∅ \Sigma_G(v) = \varnothing Σ G ( v ) = ∅ ; by Proposition 2.4 , the expanded graph still has exactly two lonely edges. Lemma 4.8 , Lemma 4.11 and Lemma 4.13 guarantee that the standard marking is updated according to the definitions. The matching type is preserved by Lemma 4.1, so starting from C 2 = \mathcal{C}_2^= C 2 = produces only graphs in U 2 = U_2^= U 2 = , while starting from C 2 ≠ \mathcal{C}_2^{\ne} C 2 = produces only graphs in U 2 ≠ U_2^{\ne} U 2 = .
Conversely, Theorem 4.20 shows that the reverse of any kernel-reduction sequence for any G ∈ U 2 G \in U_2 G ∈ U 2 is realized step by step by Operations E, C, T. If G ∈ U 2 = G \in U_2^= G ∈ U 2 = , only Operation E occurs throughout the sequence; if G ∈ U 2 ≠ G \in U_2^{\ne} G ∈ U 2 = , only Operations C and T occur. Hence all three assertions of Theorem 4.21 follow. □
Part (i) recovers the class characterized recursively in [6 Theorem 4.12] , using the complete primitive-kernel list obtained here. Parts (ii) and (iii) incorporate the unequal-matching type into the construction.
Corollary 4.22. If G ∈ U 2 = G \in\mathcal{U}_2= G ∈ U 2 = , then each of its two lonely edges lies in a triangle; the complete set of zero-loss expansion vertices is exactly the four endpoints of the two lonely edges, and those four vertices form a noninterfering set.
Proof. By Theorem 4.20 , G G G admits an equal-matching standard marking. The conclusion is precisely the content of Definition 4.5 together with Lemma 4.6 .
Corollary 4.23. If G ∈ U 2 ≠ G \in\mathcal{U}_2^{\ne} G ∈ U 2 = , then it admits at least one marking of the following form: the two lonely edges together with one center edge form a three-edge center path; the complete set of zero-loss expansion vertices consists exactly of the two center vertices and a collection of directed tips; and this zero-loss vertex set is noninterfering. A center expansion creates one new tip, while a tip extension merely moves one tip.
Proof. Choose an unequal-matching standard marking from Theorem 4.20 , and apply Definition 4.9 , Lemma 4.11 and Lemma 4.13 .
Conclusion
In this paper, we completed the classification of 3-connected cubic graphs with at least two lonely edges by giving a full structural characterization of U 2 \mathcal{U}_2 U 2 , the family of 3-connected cubic graphs with exactly two lonely edges. We identified its minimally non-contractible “primitive kernels” and developed constructive operations that generate every graph in U 2 \mathcal{U}_2 U 2 from these kernels. The equal-matching case recovers the recursive characterization of Narayana et al. [6 ] ; the center and tip operations cover the unequal-matching case. Together with the earlier characterization of U k \mathcal{U}_k U k for k ≥ 3 k \ge3 k ≥ 3 , this yields a complete description of the classes U k \mathcal{U}_k U k for all k ≥ 2 k \ge2 k ≥ 2 . A natural remaining question is how to characterize the structure of U 1 \mathcal{U}_1 U 1 .