3.1. Cohomology of a real toric variety

A toric variety of complex dimension n is a normal algebraic variety containing an algebraic torus $(\mathbb{C}^\ast)^n$ as a Zariski open dense subset such that the action of the torus on itself extends to the whole variety. A real toric variety is the real locus of a toric variety. The fundamental theorem of toric geometry says that there is a one-to-one correspondence between the class of toric varieties of complex dimension n and the class of fans in $\mathbb{R}^n$. In particular, for a complete smooth toric variety X, the corresponding fan $\Sigma_X$ is complete and smooth. Furthermore, a complete smooth toric variety X is projective if and only if $\Sigma_X$ can be realized as the normal fan of a smooth polytope in $\mathbb{R}^n$.

Although the integral cohomology ring of a complete smooth toric variety was studied by Danilov [Reference Danilov12] and Jurkiewicz [Reference Jurkiewicz13] in the late 1970s, only little is known about the cohomology of complete smooth real toric varieties. For a complete smooth toric variety X and its real locus $X^{\mathbb{R}}$, the cohomology ring $H^\ast(X^{\mathbb{R}};\mathbb{Z}_2)$ was computed by Jurkiewicz [Reference Jurkiewicz14] in 1985, and it has a similar form to the integral cohomology ring $H^\ast(X;\mathbb{Z})$. Note that the dimension of $H^i(X^{\mathbb{R}};\mathbb{Z}_2)$ as a vector space over $\mathbb{Z}_2$ is equal to h_i, where $(h_0,h_1,\ldots,h_n)$ is the h-vector of K_X, the underlying simplicial sphere of the fan $\Sigma_X$.

Recently, there were several efforts to compute the integral cohomology of a real toric variety. Let P be a smooth polytope of dimension n and let $\mathcal{F}(P)=\{F_1,\ldots,F_m\}$ be the set of facets of P. Then the primitive outward normal vectors of P can be understood as a function ϕ from $\mathcal{F}(P)$ to $\mathbb{Z}^n$, and the composition map $\lambda \colon \mathcal{F}(P) \stackrel{\phi}{\rightarrow} \mathbb{Z}^n \stackrel{\text{mod $2$}}{\longrightarrow} \mathbb{Z}_2^n$ is called the (mod 2) characteristic function over P. Note that λ can be represented by a $\mathbb{Z}_2$-matrix $\Lambda_P$ of size n × m as

\begin{equation*} \Lambda_P = \begin{pmatrix} \lambda(F_1) & \cdots & \lambda(F_m) \end{pmatrix}, \end{equation*}

where the ith column of $\Lambda_P$ is $\lambda(F_i) \in \mathbb{Z}_2^n$. For $\omega \in \mathbb{Z}_2^m$, we define P_ω to be the union of facets F_j such that the jth entry of ω is nonzero. Then the following holds:

Theorem 3.1. ([Reference Choi and Park10, Reference Trevisan19])

Let P be a smooth polytope of dimension n and $X^{\mathbb{R}}_P$ the projective smooth real toric variety associated with P. Then the Betti numbers of $X^{\mathbb{R}}_P$ is given as follows:

(3.1)\begin{equation} \beta^i(X^{\mathbb{R}}_P) = \sum_{S\subset [n]} \widetilde{\beta}^{i-1}(P_{\omega_S}), \end{equation}

where ω_S is the sum of the kth rows of $\Lambda_P$ for all $k\in S$.

For $S\subset [n]$, let $K_{P,S}$ be the simplicial subcomplex of K_P dual to $P_{\omega_S}$. Note that $K_{P,S}$ and $P_{\omega_S}$ have the same homotopy type. Hence, we can rewrite Equation (3.1) by using $K_{P,S}$:

(3.2)\begin{equation} \beta^i(X^{\mathbb{R}}_P) =\sum_{S\subset [n]} \widetilde{\beta}^{i-1}(K_{P,S}). \end{equation}

In general, the integral cohomology of $K_{P,S}$ may have p-torsion for arbitrary p > 1, and hence it is not easy to compute. Furthermore, the torsion of $H^\ast(K_{P,S};\mathbb{Z})$ influences the torsion of $H^\ast(X^{\mathbb{R}}_P;\mathbb{Z})$.

See Theorem 1.1 and Corollary 1.2 of [Reference Cai and Choi5] for more details of the above theorem.

3.2. Real toric variety arising from a graph

Given a graph G, the pseudograph associahedron P_G is first introduced in [Reference Carr, Devadoss and Forcey7] as a generalization of a graph associahedron in [Reference Carr and Devadoss6]. In this paper, we use the construction of a pseudograph associahedron in [Reference Choi, Park and Park8], slightly different from [Reference Carr, Devadoss and Forcey7]. When G is connected, our pseudograph associahedron P_G is the same as the pseudograph associahedron $\mathcal{K}G$ in [Reference Carr, Devadoss and Forcey7], but if G is disconnected, we get a different polytope. In our constructon, if G consists of connected components $G_1,\dots,G_k$, then P_G is defined to be the product $P_{G_1}\times\dots\times P_{G_k}.$Footnote ² We introduce the construction of P_G briefly.

For a graph G, we label the vertices and the multiple edges of G. We write a subgraph H of G as the set of the vertices of H and the edges of H in a bundle of G. For simplicity, we omit the braces and commas to represent a subset of $\mathcal{C}_G$ and we always denote it in a way that the vertices precede the multiple edges. We say that a subgraph H of G is induced (respectively, semi-induced) if H is a subgraph that includes all edges (respectively, at least one edge) between every pair of vertices in H, if such edges exist in G. For instance, in Figure 3.1, the four subgraphs $12a, 12b, 123a, 123b$ are semi-induced but not induced subgraphs of G. It should be noted that our set expression makes sense for a semi-induced subgraph because semi-induced subgraphs of a given graph G can be distinguishable by the corresponding set.

Figure 3.1. The proper connected semi-induced subgraphs of G and the facets of P_G

We remark that when we consider a subgraph H of a graph G, the labels of H are inherited from the labels of G. Thus, if a graph H is considered as a subgraph of a graph G, then H may have a labelled simple edge, which is not in a bundle of H (actually, it is in a bundle of G). Note that for the graph G in Figure 3.1, 12a and 12b are different objects if they are considered as semi-induced subgraphs of G.

Let G be a connected graph on the vertex set $V=[n]$ and with exactly k bundles $B_1,\dots, B_k$. Let $\Delta_V$ be the simplex $\Delta^{|V|-1}$ whose facets are labelled with the vertices of G. Then each face of $\Delta_V$ corresponds to a proper subset of vertices of G, defined by the intersection of the facets associated with those vertices.Footnote ³ For each $i=1,\ldots,k$, let $\Delta_{B_i}$ be the simplex $\Delta^{|B_i|-1}$ whose vertices are labelled with the multiple edges in B_i. Then each face of $\Delta_{B_i}$ corresponds to a subset of B_i defined by the vertices spanning the face.Footnote ⁴ Now we define $\Delta_G$ as the product of simplices

\begin{equation*}\Delta_G:=\Delta_{V}\times\Delta_{B_1}\times\cdots\times \Delta_{B_k}\end{equation*}

endowed with the labels naturally induced from the labelling on $\Delta_V$ and $\Delta_{B_i}$ ($1\leq i\leq k$). Then the pseudograph associahedron P_G is obtained from $\Delta_G$ by truncating the faces corresponding to the proper connected semi-induced subgraphs of G in increasing order of dimension.Footnote ⁵ See Figure 3.1. Then the following hold:

1. (1) There is a one-to-one correspondence between the facets F_I of P_G and the proper connected semi-induced subgraphs I of G.

2. (2) Two facets F_H and $F_{H^{\prime}}$ of P_G intersect if and only if H and Hʹ are disjoint and cannot be connected by an edge of G, or one contains the other.

If $G_1,\ldots,G_\ell$ are the connected components of G, then $P_G=P_{G_1}\times\cdots\times P_{G_\ell}$ and the dimension of P_G is

\begin{equation*} \dim P_{G}=|V(G)|-\ell+\sum_{i=1}^k(|B_i|-1), \end{equation*}

where B_i’s are all the bundles of G. See [Reference Choi, Park and Park8, §2], where the readers may find examples, definitions and a much more detailed account of results for pseudograph associahedra.

Note that

• • a product of smooth polytopes is a smooth polytope,

• • any face of a smooth polytope is a smooth polytope, and

• • for a smooth polytope P and a proper face F, there is a canonical truncation of P along F such that the result is a smooth polytope. (See [Reference Choi, Park and Park8, Lemma 2.5].)

For a connected graph G, since $\Delta_G$ is a smooth polytope, the pseudograph associahedron P_G can be realized as a smooth polytope canonically. In particular, the normal vector of the facet corresponding to a proper connected semi-induced subgraph H of G is determined by the label of H. Hence, under the canonical smooth realization, we get the projective smooth toric variety $X_G:=X_{P_G}$ and the projective smooth real toric variety $X^{\mathbb{R}}_G:=X_{P_G}^{\mathbb{R}}$, associated with a graph G. For example, it is known that if G is the simple path graph P ₃, then the polytope P_G is a pentagon. Hence, X_G is $\mathbb{C} P^2\#2\overline{\mathbb{C} P^2}$, obtained from $\mathbb{C} P^2$ by blowing up two fixed points; $X^{\mathbb{R}}_G$ is $\#3\mathbb{R}P^2$, the connected sum of three copies of the real projective plane $\mathbb{R}P^2$. If G is the graph with two vertices and two multiple edges, then X_G is $\mathbb{C} P^1\times \mathbb{C} P^1$ and $X_G^{\mathbb{R}}$ is $\mathbb{R} P^1\times \mathbb{R} P^1$.Footnote ⁶

3.3. A poset of even subgraphs

For a graph G, a graph H is a partial underlying graph of G if H can be obtained from G by replacing some bundles with simple edges, that is, the set of all the bundles of H is a subset of G. A graph H is a partial underlying induced graph (PI-graph for short) of G if H is an induced subgraph of some partial underlying graph of G. Note that a graph is a PI-graph of itself. For instance, for the graph G with two bundles $\{a,b\}$ and $\{c,d,e\}$ in Figure 3.2,

• • $H_1, H_2$ and H ₃ are partial underlying graphs of G, and

• • all H_i’s are PI-graphs of G.

Figure 3.2. Examples for PI-graphs of G and the posets $\mathcal{P}_{H,A}^{\mathrm{even}}$.

For a graph G, we let $\mathcal{C}_G$ be the set of all labels of G, i.e., $\mathcal{C}_G=V(G)\cup B_1\cup \cdots \cup B_k$, where $B_1,\ldots,B_k$ are the bundles of G. For instance, $\mathcal{C}_G=\{1,2,3,4,a,b,c,d,e\} $ and $\mathcal{C}_{H_3}=\{1,2,3,4,c,d,e\}$ for the graphs G and H ₃ in Figure 3.2.

Let $\mathcal{A}(H)$ denote the set of all the admissible collections of H. The set of admissible collections each of the graphs H_i’s in Figure 3.2 are as follows:

\begin{equation*}\begin{array}{lll} \mathcal{A}(H_1)=\{1234\}, &\mathcal{A}(H_2)=\{34ab, 1234ab\},&\mathcal{A}(H_3)=\left\{14cd, 14ce, 14de, 1234cd,\right.\\ && \qquad \qquad \left.1234ce, 1234de\right\},\\ \mathcal{A}(H_4)=\emptyset, &\mathcal{A}(H_5)=\{13ab, 23ab\}, &\mathcal{A}(H_6)=\left\{12cd, 12ce, 12de, 13cd,\right.\\ && \qquad \qquad \left. 13ce, 13de\right\},\\ \end{array}\end{equation*}

Let $A\subset \mathcal{C}_H$. We say that a semi-induced subgraph I of H is A-even (respectively, A-odd) if $|A\cap I^{\prime}|$ is even (respectively, odd) for every connected component Iʹ of I.Footnote ⁷ Then we define the poset $\mathcal{P}_{H,A}^{\mathrm{even}}$ as follows. If $A \in \mathcal{A}(H)$, then the poset $\mathcal{P}_{H,A}^{\mathrm{even}}$ is defined to be the poset consisting of all A-even semi-induced subgraphs of H ordered by the subgraph containment, including both $\emptyset$ and H. Hence, $\mathcal{P}_{H,A}^{\mathrm{even}}$ is a bounded poset. If $A\not \in \mathcal{A}(H)$, then we define $\mathcal{P}_{H,A}^{\mathrm{even}}$ by the null poset. Figure 3.2 shows (the Hasse diagram of) the posets $\mathcal{P}_{H_1,1234}^{\mathrm{even}}, \mathcal{P}_{H_2,1234ab}^{\mathrm{even}}$ and $\mathcal{P}_{H_3,1234cd}^{\mathrm{even}}$. Note that the first two posets are shellable but the last is not. For more examples of $\mathcal{P}_{H,A}^\mathrm{even}$, see also Figure 5.3.

Combining Lemma 4.5 with Proposition 4.7 of [Reference Choi, Park and Park8], it holds the following.

For the sake of convenience, we put a sketch of the proof of Proposition 3.4 in Appendix.

For a graph H, it was also noted in [Reference Choi, Park and Park8, §5] that $\Delta(\overline{\mathcal{P}_{H,A}^{\mathrm{even}}})$ (respectively, $\Delta(\overline{\mathcal{P}_{H,A}^{\mathrm{odd}}})$) is a geometric subdivision of the simplicial complex dual to the union of the facets F_I of the polytope P_H such that $|I\cap A|$ is even (respectively, odd). Hence, from the Alexander duality, we have

(3.3)\begin{equation} \widetilde{H}^{i}\left(\Delta\left(\overline{\mathcal{P}_{H,A}^{\mathrm{odd}}}\right);\mathbb{Z}\right) \cong\widetilde{H}_{\dim(P_H)-i-2}\left(\Delta\left(\overline{\mathcal{P}_{H,A}^{\mathrm{even}}}\right);\mathbb{Z}\right). \end{equation}

Therefore, if $K_{P_G,S}$ is homotopy equivalent to $\Delta(\overline{\mathcal{P}_{H,A}^{\mathrm{odd}}})$ and $\mathcal{P}_{H,A}^{\mathrm{even}}$ is shellable, then $\widetilde{H}^\ast(K_{P_G,S};\mathbb{Z})$ is torsion-free.

Let H be a simple graph. Then $\mathcal{A}(H)=\{H\}$ if each connected component of H has an even number of vertices, and $\mathcal{A}(H)=\emptyset$ otherwise. Thus, we write $\mathcal{P}_H^{\mathrm{even}}$ instead of $\mathcal{P}_{H,H}^{\mathrm{even}}$.

Recall that a pure and totally semimodular poset is CL-shellable by Theorem 2.1-(3). Hence, $\mathcal{P}_H^{\mathrm{even}}$ is CL-shellable for every simple graph H.

In [Reference Choi, Park and Park8], there was an effort to extend results of [Reference Choi and Park9] for a simple graph to a graph allowing multiple edges. Almost all results of [Reference Choi and Park9] except for Theorem 3.5 were well-extended by using $\mathcal{P}_{H,A}^{\mathrm{even}}$, where H is a PI-graph of G and $A\in\mathcal{A}(H)$. In fact, since the poset $\mathcal{P}_{H_3,1234cd}^{\mathrm{even}}$ in Figure 3.2 is not shellable, Theorem 3.5 cannot be generalized to $\mathcal{P}_{H,A}^{\mathrm{even}}$. Hence, it is natural to ask which $\mathcal{P}_{H,A}^{\mathrm{even}}$ is shellable. Taking an interest in a projective smooth real toric variety associated with a graph, the following Question 1.2 was asked in [Reference Choi, Park and Park8]. For a graph G, let $\mathcal{A}^\ast(G)=\{(H,A)\mid H \text{is a PI-graph of $G$ and }A\in \mathcal{A}(H) \}.$

Question 1.2. ([Reference Choi, Park and Park8]) Find all graphs G such that $\mathcal{P}_{H,A}^{\mathrm{even}}$ is shellable for every $(H,A) \in \mathcal{A}^{\ast}(G)$.

For simplicity, throughout the paper, let $\mathcal{G}^{\ast}$ be the family of all graphs G such that $\mathcal{P}_{H,A}^{\mathrm{even}}$ is shellable for every $(H,A) \in \mathcal{A}^{\ast}(G)$. Clearly, the family $\mathcal{G}^\ast$ contains all simple graphs by Theorem 3.5. The answer to Question 1.2 is the following, which restates Theorem 1.3.

Theorem 1.3. A graph G is in $\mathcal{G}^*$ if and only if each connected component of G is either a simple graph or one of the graphs in Figure 1.1.

By Theorem 1.3, for every $G\in\mathcal{G}^\ast$, each poset $\mathcal{P}_{H,A}^{\mathrm{even}}$ is shellable, and hence $\Delta(\overline{\mathcal{P}_{H,A}^{\mathrm{even}}})$ is homotopy equivalent to a wedge of spheres. Thus, $\widetilde{H}^\ast(K_{P_G,S};\mathbb{Z})$ is torsion-free for every subset S of the set of integers $\{1,2,\dots,\dim P_{G}\}$, and we get the following from [Reference Cai and Choi5, Corollary 1.2].

Corollary 3.6. For a graph $G\in\mathcal{G}^\ast$, the integral cohomology of the projective smooth real toric variety $X^{\mathbb{R}}_G$ is torsion-free or has only 2-torsion elements:

\begin{equation*}H^i\left(X^{\mathbb{R}}_G;\mathbb{Z}\right)=\mathbb{Z}^{\beta^i}\oplus\mathbb{Z}_2^{h_i-\beta^i},\end{equation*}

where $\beta^i=\beta^i(X^{\mathbb{R}}_G)$ and $h_i=h_i(P_G)$.

As an immediate consequence of the proof in §5, we also get the following:

We finish the section by giving a remark that it is sufficient to consider a connected graph to prove Theorem 1.3 and Theorem 3.7. To see why, let $G_1, \ldots, G_k$ be the connected components of a graph G. Note that for a subgraph H of G and $A\in\mathcal{C}_H, (H,A)\in\mathcal{A}^{\ast}(G)$ if and only if $(H\cap G_i, A\cap \mathcal{C}_{G_i})\in \mathcal{A}^\ast(G_i)$ for each i. Thus, for each $(H,A)\in\mathcal{A}^{\ast}(G)$, $\mathcal{P}_{H,A}^{\mathrm{even}}$ is isomorphic to the product $\mathcal{P}_{H_1,A_1}^{\mathrm{even}}\times \cdots \times \mathcal{P}_{H_k,A_k}^{\mathrm{even}}$, where $H_i=H\cap G_i$ and $A_i=A\cap \mathcal{C}_{G_i}$ for each i. By (2) of Theorem 2.1, $\mathcal{P}_{H,A}^{\mathrm{even}}$ is shellable if and only if $\mathcal{P}_{H_i,A_i}^{\mathrm{even}}$ is shellable for each i. Thus, $G\in \mathcal{G}^\ast$ if and only if $G_i\in \mathcal{G}^\ast$ for each i.

5.1. Definition of an ordering $\prec_{\tiny\text{atm}}^{I}$ for the atoms of $[I,G]$

We let $V=\{1,2,\ldots,n\}$ $(n\ge 2)$ be the set of vertices of G, and 1 and 2 be the endpoints of the bundle B. By the definition of an admissible collection, note that $\{3,\ldots,n\} \subset A$, $A\cap B\neq\emptyset$ and $|A\cap B|$ is even, so we let $B\cap A=\{a_1,\ldots,a_{2m}\}$ ($m\ge 1$) and $B\setminus A=\{b_1,\ldots,b_\ell\}$. Here, $B\setminus A$ may be the empty set. There are three cases:

• • $|V|$ is odd and $ V\cap A = V \setminus \{w\} $ for some $w\in\{1,2\}$;

• • $|V|$ is even and $ V\cap A = V \setminus \{1,2\}$;

• • $|V|$ is even and $ V\cap A = V$.

We label the vertices that are not the endpoints of B so that for each $i\in \{3,\ldots,n\}$, the vertex i is closest to the vertex i − 1. We relabel the endpoints of B so that $1\not\in A$ if $|V|$ is odd and 13 is an edge if $|V|$ is even. See (i) of Figure 5.2 for all the possible labellings when $|V|$ is odd. We illustrate all the possible labellings when $|V|$ is even in (ii) of Figure 5.2. See Figure 5.3 for examples of $\mathcal{P}_{G,A}^{\mathrm{even}}$ under this labelling. We also assume that there is a total ordering between the vertices: $1\prec 2 \prec \cdots \prec n$. Thus, for $I\subset V$, the minimum of I, denoted by $\min(I)$, means the frontmost one in the ordering.

Figure 5.2. Labelling of the vertices.

Figure 5.3. Examples of posets $\mathcal{P}_{G,A}^{\mathrm{even}}.$

Note that given a cover $I\lessdot J$ in $\mathcal{P}_{G,A}^{\mathrm{even}}$, if $(J\setminus I)\cap B\neq\emptyset$, then either $(J\setminus I)\cap (B\cap A)=\emptyset$ or $(J\setminus I)\cap (B\setminus A)=\emptyset$. Suppose not, that is, $(J\setminus I)\cap (B\cap A)\neq\emptyset$ and $(J\setminus I)\cap (B\setminus A)\neq\emptyset$. Then $K:=J\setminus \{(J\setminus I)\cap (B\setminus A)\}$ satisfies that $I \lt K \lt J$ and $|(K\setminus I)\cap A|\equiv|(J\setminus I)\cap A|$, a contradiction to $I\lessdot J$. Hence, we can define the type of a cover $I\lessdot J$ in $\mathcal{P}_{G,A}^{\mathrm{even}}$ according to the size of $J\setminus I$ and the intersection with $B\setminus A$. A cover $I\lessdot J$ has type (Ei) if $|J\setminus I|=i$ and $J\setminus I$ has no element of $B\setminus A$; $I\lessdot J$ has type (E${i}^{\prime}$) if $|J\setminus I|=i$ and $J\setminus I$ contains some elements of $B\setminus A$. Hence, (E$i{}^\prime$) can occur only when $B\setminus A\neq \emptyset$.

Lemma 5.1. Let $I\lessdot J$ be a cover in $\mathcal{P}_{G,A}^{\mathrm{even}}$. Then $J\setminus I$ is one of the sets represented in Table 1.

Table 1. Types of $I\lessdot J$ in $\mathcal{P}_{G,A}^{\mathrm{even}}$, where $a,\,a^{\prime}\in B\cap A$, $b\in (B\setminus A)$, c, $c^{\prime}\in A$, $v=\min(V\setminus (I\cup\{1,2\}))$

For the case of (E3), $c\in B\cap A$ or $c=\min(V\setminus (I\cup\{1,2\}))$.

When $I\lessdot J$ is of (E3${}^\prime$), as in Table 1, we divide the type (E3${}^\prime$) into two subtypes according to the size of $(J\setminus I)\cap \{1,2\}$:

• • $I\lessdot J$ has type (E3${}^{\prime}$-1) if $I\lessdot J$ has type (E3${}^{\prime}$) and $|(J\setminus I)\cap \{1,2\}|=1$;

• • $I\lessdot J$ has type (E3${}^{\prime}$-2) if $I\lessdot J$ has type (E3${}^{\prime}$) and $|(J\setminus I)\cap \{1,2\}|=2$.

We can also show that when $I\lessdot J$ is of (E3${}^{\prime}$-1), $J\setminus I$ contains the vertex $\min(V\setminus (I\cup\{1,2\}))$.

Proposition 5.2. The lengths of maximal chains of $\mathcal{P}_{G,A}^{\mathrm{even}}$ are

\begin{equation*}\begin{cases} \frac{|A|}{2}+|B\setminus A|+1 \ \text{or }\ \frac{|A|}{2}+ |B\setminus A| & \text{if }|V|\text{is odd,}\\ \frac{|A|}{2}+|B\setminus A|+1 & \text{if }|V|\text{is even and }A\cap V\neq V, {and}\\ \frac{|A|}{2}+|B\setminus A| \ \text{or }\ \frac{|A|}{2}+|B\setminus A|-1& \text{if }|V|\text{is even and }A\cap V = V. \end{cases} \end{equation*}

Moreover, if $|V|$ is odd, 2 and 3 are not adjacent in G and $B\subset A$, then $\mathcal{P}_{G,A}^{\mathrm{even}}$ is pure and its length is $\frac{|A|}{2}+1$.

Proof. Recall that $|V|=n, |B\cap A|=2m$ and $|B\setminus A|=\ell$. Note that $2m+n\ge 4$. Let $\sigma\colon I_0\lessdot I_1\lessdot\cdots\lessdot I_p$ be a maximal chain of $\mathcal{P}_{G,A}^{\mathrm{even}}$. Note that $\{I_i\setminus I_{i-1} \mid i=1,\ldots,p \}$ is a partition of $V\cup B$.

Let k be the smallest index such that $I_{k}\setminus I_{k-1}$ contains an element in B, that is, I_k is the first element of σ containing a multiple edge. Then $\{1,2\}\subset I_k$ and $\{1,2\}\not\subset I_{k-1}$. Together with Table 1, we see that for each cover $I_{i-1}\lessdot I_i$ of σ, except the cover $I_{k-1}\lessdot I_k$, it holds that $|I_{i}\setminus I_{i-1}|=1$ or 2. For each $j\in\{1,2\}$, let t_j be the number of covers $I_{i-1}\lessdot I_i$ of σ, except the cover $I_{k-1}\lessdot I_k$, such that $|I_{i}\setminus I_{i-1}|=j$. Then the number of covers of σ, which is equal to $\ell(\sigma)$, is $1+t_1+t_2$. Since $\{I_i\setminus I_{i-1} \mid i=1,\ldots,p \}$ is a partition of $V\cup B$, we have

\begin{equation*} t_1 +2t_2 +|I_k\setminus I_{k-1}|= |I_p\setminus I_{0}|=n+2m+\ell, \end{equation*}

or $t_2=\frac{(n+2m+\ell)-t_1-|I_k\setminus I_{k-1}|}{2}$. Therefore,

(5.1)\begin{eqnarray} &&\ell(\sigma)=1+t_1+t_2 = \frac{(n+2m+\ell)+2+t_1-|I_k\setminus I_{k-1}|}{2}. \end{eqnarray}

Note that σ has exactly $ |B\setminus (A\cup I_k)|$ covers of (E1${}^{\prime}$) and at most one cover of (E1). In addition, σ has one cover of (E1) if and only if $I_{k-1}$ contains a vertex in $\{1,2\}\setminus A$. Since t ₁ is the sum of the number of covers of (E1) and the number of covers of (E1${}^{\prime}$), we get

(5.2)\begin{eqnarray} &&t_1=\begin{cases} 1+|B\setminus (A\cup I_k)| &\text{if }I_{k-1} \text{ contains a vertex in }\{1,2\}\setminus A,\\ |B\setminus (A\cup I_k)| &\text{otherwise}. \end{cases} \end{eqnarray}

Suppose that $|V|$ is odd. Then $|A|=2m+n-1$. By Table 1 again, $I_{k-1}\lessdot I_{k}$ has one of types (E2), (E3), (E2${}^{\prime}$) and (E3${}^{\prime}$-1). By Equations (5.1) and (5.2),

\begin{equation*}\ell(\sigma)=\begin{cases} \frac{(n+2m+\ell)+2+(1+\ell)-2}{2} = \ell+1+\frac{n+2m-1}{2}=\ell+1+\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E2)},\\ \frac{(n+2m+\ell)+2+\ell-3}{2}=\ell+\frac{n+2m-1}{2} =\ell +\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E3)},\\ \frac{(n+2m+\ell)+2+(\ell-1)-2}{2}=\ell+\frac{n+2m-1}{2}=\ell +\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E2${}^{\prime}$)},\\ \frac{(n+2m+\ell)+2+(1+(\ell-1))-3}{2}=\ell+\frac{n+2m-1}{2}=\ell +\frac{|A|}{2} & \text{if }I_{k-1}\lessdot I_{k} \text{ is of (E3${}^{\prime}$-1)}. \end{cases}\end{equation*}

Hence, every maximal chain has a length of either ${\frac{|A|}{2}+\ell+1}$ or ${\frac{|A|}{2}+\ell}$, and hence the poset $\mathcal{P}_{G,A}^{\mathrm{even}}$ is nonpure. Note that if 2 and 3 are not adjacent in G, then there is no cover of (E3), and if $B\subset A$, then $B\setminus A=\emptyset$ and then there is no cover of (E2${}^\prime$) or (E3${}^\prime$). Hence, if 2 and 3 are not adjacent in G and $B\subset A$, then $\mathcal{P}_{G,A}^{\mathrm{even}}$ is a pure poset of length ${\frac{|A|}{2}+1}$. We summarize in the following table:

Suppose that $|V|$ is even. When $A\cap \{1,2\}=\emptyset$, it holds that $|A|=2m+n-2$ and $I_{k-1}\lessdot I_{k}$ is of (E3) or (E2${}^{\prime}$). By Equations (5.1) and (5.2),

\begin{equation*}\ell(\sigma)=\begin{cases} \frac{(n+2m+\ell)+2+(1+\ell)-3}{2} = \ell+1+\frac{n+2m-2}{2}=\ell+1+\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E3)},\\ \frac{(n+2m+\ell)+2+(1+(\ell-1))-2}{2}=\ell+1+\frac{n+2m-2}{2} =\ell +1+\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E2${}^{\prime}$)}. \end{cases}\end{equation*}

Hence, every maximal chain has length $\frac{|A|}{2}+\ell+1$.

When A contains $\{1,2\}$, it holds that $|A|=2m+n$ and $I_{k-1}\lessdot I_{k}$ is one of (E2), (E4) and (E3${}^{\prime}$). By Equation (5.1) and (5.2),

\begin{equation*}\ell(\sigma)=\begin{cases} \frac{(n+2m+\ell)+2+\ell-2}{2} = \ell+\frac{n+2m}{2}=\ell+\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E2)},\\ \frac{(n+2m+\ell)+2+\ell-4}{2} = \ell-1+\frac{n+2m}{2}=\ell-1+\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E4)},\\ \frac{(n+2m+\ell)+2+(\ell-1)-3}{2}=\ell-1+\frac{n+2m}{2} =\ell-1+\frac{|A|}{2} &\text{if }I_{k-1}\lessdot I_{k} \text{ is of (E3${}^{\prime}$)}. \end{cases}\end{equation*}

Hence, every maximal chain has length $\ell+\frac{|A|}{2} $ or $\ell-1+\frac{|A|}{2}$. We summarize in the following table:

We shall show that $\mathcal{P}_{G,A}^{\mathrm{even}}$ admits a recursive atom ordering. We first define the lexicographic order $\prec_{\tiny\text{lex}}^{I}$ on $V\cup B$ for each $I\in \mathcal{P}_{G,A}^{\mathrm{even}}$ and then define the atom ordering $\prec_{\tiny\text{atm}}^{I}$ for $[I,G]$.

Here is an example. Let G be the graph $\widetilde{P}_{6,5}$ in Figure 1.1. Suppose that $A=V \cup \{a_1,a_2,a_3,a_4\}$. Then the atoms of $\mathcal{P}_{G,A}^{\mathrm{even}}$ are ordered as follows:

\begin{equation*}\prec_{\tiny\text{atm}}^{\emptyset}: \ 13, \ 12a_1a_2, \ 12a_1a_3 , \ 12a_1a_4, \ 12a_2a_3, \ 12a_2a_4 , \ 12a_3a_4, \ 12b_1, \ 34, \ 45, \ 56.\end{equation*}

For $I=12a_1a_3$, $\prec_{\tiny\text{lex}}^{I}: 1, 2,a_1,{\bf a_2},a_3,{\bf 3},{\bf 4},{\bf 5},{\bf 6},{\bf a_4},{\bf b_1}$, and the atoms of $[I,G]$ are ordered as follows:

\begin{equation*}\prec_{\tiny\text{atm}}^{I}: 12{\bf 3}a_1{\bf a_2}a_3, \ 12a_1{\bf a_2}a_3{\bf a_4}, \ 12\bf{34}a_1a_3,\ 12{\bf 3}a_1a_3{\bf a_4}, \ 12\bf{45}a_1a_3, \ 12\bf{56}a_1a_3, 12a_1a_3{\bf b_1} \end{equation*}

because $a_23\prec_{\tiny\text{lex}}^{I}a_2a_4\prec_{\tiny\text{lex}}^{I}34\prec_{\tiny\text{lex}}^{I}3a_4\prec_{\tiny\text{lex}}^{I}45\prec_{\tiny\text{lex}}^{I}56\prec_{\tiny\text{lex}}^{I}b_1$, where the bold letters indicate the elements not in I.

The following is the main theorem of this section, whose proof is given in §5.2.

5.2. Proof of Theorem 5.4

For a subset $X\subset V\cup B$, $\min^{I}(X)$ and $\max^{I}(X)$ denote the minimum and the maximum of X with respect to $\prec_{\tiny\text{lex}}^{I}$, respectively. We will show that the ordering $\prec_{\tiny\text{atm}}^{I}$ ($I\in \mathcal{P}_{G,A}^{\mathrm{even}}$) is a recursive atom ordering. We first check Condition (2) of Definition 2.3.

Lemma 5.5. Let I_i and I_j be atoms of $[I,G]$ such that $I_i\prec_{\tiny\text{atm}}^{I} I_j$. If there is an element K of $[I,G]$ such that $I_i, I_j \lt K$, then there exists an atom $K_\ast$ of $[I_j,G]$ and an atom $I_\ast$ of $[I,G]$ such that

\begin{equation*}K_\ast\le K, \quad K_\ast\in [I_\ast,G],\quad\text{and }\quad I_\ast\prec_{\tiny\text{atm}}^{I} I_j.\end{equation*}

Proof. Let $K_0=I_i\cup I_j$ for simplicity. Note that $K_0\subset K$, and one can check from Lemma 5.1 that there is no element $L\in \mathcal{P}_{G,A}^{\mathrm{even}}$ such that $I_j \subsetneq L \subsetneq K_0$.

(Case 1) K ₀ is not a semi-induced subgraph of G. Note that a subset of $V\cup B$ is not a semi-induced subgraph if and only if it contains $\{1,2\}$ and has no element in B. Then $I_i\setminus I$ and $I_j\setminus I$ contain exactly one of the endpoints of B, not the same. More precisely, letting $v=\min(V\setminus (I\cup\{1,2\}))$, one of the following holds:

\begin{equation*} \begin{array}{lll} I_i\setminus I=1 &\text{and }\quad I_j\setminus I=2v &\text{if }A\cap\{1,2\}=\{2\},\\ I_i\setminus I=1 &\text{and }\quad I_j\setminus I=2 &\text{if }A\cap\{1,2\}=\emptyset,\\ I_i\setminus I=1v &\text{and }\quad I_j\setminus I=2v &\text{if }A\cap\{1,2\}=\{1,2\}.\\ \end{array}\end{equation*}

Note that $I_j\setminus I=2v$ occurs only when 2 and 3 are adjacent in G. Moreover, if $I_i\setminus I=1v_1$ and $I_j\setminus I=2v_2$ hold, then I is a simple connected graph with even number of vertices, so $v_1=v_2=v$. Indeed, if G is $\tilde{P}^{\prime}_{n,m}$, then $v_1=v_2=v$ by the structure of a path. If G is $ \tilde{S^{\prime}}_{n,m}$ or $\tilde{T}^{\prime}_{n,m}$ ($n\geq 5$, odd), then $v_1\neq v_2$ only when $I=V\setminus\{1,2,n-1,n\}$. However, since n is odd, I has an odd number of vertices. This is a contradiction. In addition, $1\not\in A$ if and only if $|K_0\cap A|\equiv |(K_0\setminus I)\cap A|\equiv 0\pmod{2}$. Since K has both 1 and 2, it should have a multiple edge e. We find $K_\ast$ and $I_\ast$ according to the parity of $|A\cap\{1,e\}|$.

(Subcase 1) $\underline{|A\cap\{1,e\}|\equiv 0\pmod{2}}$. In this case, $K_\ast=K_0\cup e=I_j\cup 1e$ and $I_\ast=I_i$.

(Subcase 2) $\underline{|A\cap\{1,e\}|=1}$. We consider the connected component H of K containing e. Since $e\in H\setminus K_0$, $|K_0\cap A|\equiv|H\cap K_0\cap A|\equiv|(H\setminus K_0)\cap A|$, where the first equivalence follows from the definition of H and the second equivalence comes from $|H\cap A|\equiv 0\pmod{2}$. Hence, $1\not\in A$ if and only if $|(H\setminus K_0)\cap A|$ is even. Let $X=(H\setminus K_0)\cap A$ for simplicity. If $|X|$ is even, then $1\not\in A$ and $e\in A$, and therefore, $|X\setminus\{e\}|\geq 1$. If $|X|$ is odd, then $1\in A$ and $e\not\in A$, and therefore, $|X\setminus \{e\}|=|X|\geq 1$. Hence, in any case, we can take an element $c\in X\setminus\{e\}$ so that $K_\ast=K_0\cup ce=I_j\cup 1ce$ and $I_\ast=I_i$. More precisely, either c is the vertex $\min(V\setminus (I_j\cup\{1,2\}))$ or belongs to $(B\cap A)\setminus{e}$.

(Case 2)K ₀ is a semi-induced subgraph of G. Note that $(I_i\setminus I) \cap (I_j\setminus I)\cap A$ is nonempty and has at most three elements.

(Subcase 1) $\underline{|(I_i\setminus I) \cap (I_j\setminus I)\cap A|}$ is even. In this case,

\begin{equation*}|K_0\cap A|=|I_i\cap A|+|I_j\cap A|-|(I_i\cap I_j)\cap A|=|I_i\cap A|+|I_j\cap A|-|I\cap A|-|(I_i\setminus I) \cap (I_j\setminus I)\cap A|,\end{equation*}

and therefore $|K_0\cap A|$ is even. By ($\dagger$) in the proof of Lemma 5.1, $K_0=I_j\cup (I_i\setminus I_j)$ is an atom of $[I_j,G]$, so $K_{\ast}=K_0$ and $I_{\ast}=I_i$.

(Subcase 2) $\underline{|(I_i\setminus I) \cap (I_j\setminus I)\cap A|}$ is odd. Then $|(I_i\setminus I) \cap (I_j\setminus I)\cap A|$ is one or three. Since $(I_i\setminus I) \cap (I_j\setminus I)\cap A \neq \emptyset$, the elements in $K_0\setminus I$ lie on the same connected component of K ₀ by ($\dagger$). Thus, K ₀ has exactly one connected component H ₀ such that $|H_0\cap A|$ is odd. Note that for the connected component H of K containing H ₀, we have $|(H\setminus H_0)\cap A| \ge 1$ since $|H\cap A|$ is even.

(i) If H ₀ contains a multiple edge, then there exists an element $c\in (H\setminus H_0)\cap A$ such that $K_\ast=K_0 {\cup c}$ and $I_\ast=I_i$. More precisely, if $(H\setminus H_0)\cap B\cap A\neq\emptyset$, then $c\in B\cap A$; otherwise, c is the vertex $\min(V\setminus H_0)$.

(ii) Suppose that H ₀ has no multiple edges. Then both $I_i\setminus I$ and $I_j\setminus I$ consist of two vertices in A, and $|(I_i\setminus I)\cap (I_j\setminus I)\cap A|=1$. Since H ₀ is a semi-induced subgraph of G and $|H_0\cap A|$ is odd, $(H\setminus H_0)\cap V\neq \emptyset$. If $(H\setminus H_0)\cap V$ has a vertex in $\{3,\ldots,n\}$, then by the structure of G, it is easy to see that there is a vertex v in $(H\setminus H_0)\cap \{3,\ldots,n\}$ such that $K_{\ast}=K_0\cup v$ and $I_{\ast}=I_i$. Hence, we only need to consider the case in which ${(H\setminus H_0)\cap V}\subset\{1,2\}$. If ${(H\setminus H_0)\cap V}=\{1,2\}$, then

\begin{equation*}\begin{cases} K_\ast=I_j\cup 1 \text{ and } I_\ast=I\cup 1&\text{if }1\not\in A\\ K_\ast=K_0\cup 1 \text{ and } I_\ast=I_i &\text{if }1\in A. \end{cases}\end{equation*}

It remains to consider the case where $(H\setminus H_0)\cap V=\{1\}$ or $\{2\}$. Let $(H\setminus H_0)\cap V=\{w_1\}$, and let w ₂ be the other vertex in $\{1,2\}$. If H ₀ does not contain w ₂, then $H=H_0\cup w_1$ and $w_1\in A$ (and therefore, w ₁ must be a neighbour of 3 since H is an element of $\mathcal{P}_{G,A}^{\mathrm{even}}$), and hence $K_\ast=K_0\cup w_1$ and $I_\ast=I_i$. The remaining case is that H ₀ contains w ₂. Then H contains a multiple edge, that is, $(H\setminus H_0) \cap B=H\cap B\neq \emptyset$. Hence,

\begin{equation*} 1\le|H\cap B|=|H\cap B\cap A|+|H\cap (B\setminus A)|.\end{equation*}

Since $|(H\setminus H_0)\cap A|$ is odd and

\begin{equation*}|(H\setminus H_0)\cap A| = |(H\setminus H_0)\cap V\cap A| + | (H\setminus H_0) \cap B\cap A|=|\{w_1\}\cap A| + | (H\setminus H_0) \cap B\cap A| ,\end{equation*}

we see

\begin{equation*}\begin{cases} |H\cap B\cap A|\ge 1 &\text{if } w_1\not\in A,\\ |H\cap B\cap A|\ge 2 &\text{if } w_1\in A \text{ and } H\cap (B\setminus A)=\emptyset\\ |H\cap (B\setminus A)|\ge 1 &\text{otherwise.} \end{cases}\end{equation*}

Now there are two possibilities: (a) $w_1\not\in A$ and (b) $w_1\in A$. In (a), it easily follows that $K_\ast=K_0\cup w_1a$ and $I_\ast=I_i$ for some $a\in H\cap B\cap A$. In (b), we prove it by dividing two subcases whether $w_2\in I$ or not. If $w_2\in I$, then

\begin{equation*}\begin{cases} K_\ast=I_j\cup w_1aa^{\prime} \text{ and } I_\ast=I\cup w_1a \text{ for some } a,a^{\prime}\in H\cap B\cap A&\text{if } {H}\cap (B\setminus A)=\emptyset,\\ K_\ast=K_0\cup w_1b \text{ and } I_\ast=I_i \text{ for some }b\in H\cap(B\setminus A)&\text{if } {H}\cap(B\setminus A)\neq\emptyset. \end{cases}\end{equation*}

If $w_2\not\in I$, then $w_2\in (I_i\setminus I) \cup (I_j\setminus I)$. Since $I_i\prec_{\tiny\text{atm}}^{I} I_j, w_2\in I_i$. Moreover, by the structure of G, $I_i\setminus I=w_2v$ and $I_j\setminus I=vv^{\prime}$ for $v=\min(V\setminus (I\cup \{1,2\} ))$ and $v^{\prime}=\min(V\setminus (I\cup\{1,2,v\}))$. Hence,

\begin{equation*}\begin{cases} K_\ast=I_j\cup 12aa^{\prime} \text{ and }I_\ast=I \cup 12aa^{\prime} \text{ for some } a,a^{\prime}\in H\cap B\cap A& \text{if } H\cap (B\setminus A)=\emptyset,\\ K_\ast=I_j\cup 12b \text{ and }I_\ast=I \cup 12b \text{ for some }b\in H\cap (B\setminus A)& \text{if }H\cap (B\setminus A)\neq\emptyset. \end{cases}\end{equation*}

This completes the proof.

For an element I of $\mathcal{P}_{G,A}^{\mathrm{even}}$, a multiple edge e is called a big (respectively, small) edge of I if $e \succ^{I}_{\mathrm{lex}} n$ (respectively, $e\preceq_{\tiny\text{lex}}^{I} n$). Note that if e is a small edge of I, then $e\prec_{\tiny\text{lex}}^{I} 3$. Now we check that $\prec_{\tiny\text{atm}}^{I}$ satisfies Condition (1) of Definition 2.3.

For an atom I_j of $[I,G]$, suppose that an atom J of $[I_j,G]$ belongs to $[I_\ast,G]$ for some atom $I_\ast$ of $[I,G]$ with $I_\ast\prec_{\tiny\text{atm}}^{I} I_j$ if and only if $\min^{I_j}(J\setminus I_j) \prec_{\tiny\text{lex}}^{I_j} z$ for some $z\in V\cup B$. Then the atoms J belonging to $[I_\ast,G]$ for some atom $I_\ast$ of $[I,G]$ with $I_\ast\prec_{\tiny\text{atm}}^{I} I_j$ come first in the order $\prec^{I_j}_{\mathrm{atm}}$. Hence, the following lemma says that $\prec_{\tiny\text{atm}}^{I}$ satisfies Condition (1) of Definition 2.3.

Proof. In each case, when we show the ‘if’ part, we show that there exists an atom $I_\ast$ $[I,G]$ such that $J\in [I_\ast,G]$ and $I_\ast\prec_{\tiny\text{atm}}^{I} I_j$. On the other hand, we prove the ‘only if’ part by contradiction. Set $x=\min^{I_j}(J\setminus I_j)$.

(1) Suppose that $I_j\setminus I\subset V$ and $(I_j\setminus I)\cap\{1,2\}\neq\emptyset$. Note that

\begin{equation*}\prec_{\tiny\text{lex}}^{I}: \ 1,2,\ldots,{n},a_1,\ldots,a_{2m},b_1,\ldots,b_\ell.\end{equation*}

Since we assumed I_j is not the first atom of $[I,G]$, we have $(I_j\setminus I)\cap\{1,2\}=\{2\}$. Suppose that $x\prec_{\tiny\text{lex}}^{I_j} 2$. Then x = 1, and

\begin{equation*} J\setminus I_j = \left\{\begin{array}{ll} 1ac\text{ or }1b, &\text{if }1\not\in A,\\ 1a\text{ or }1{v}b & \text{if }1\in A, \end{array}\right. \end{equation*}

where $a\in B\cap A$, $c\in A$, $b\in B\setminus A$ and ${v}=\min(V\setminus (I_j\cup\{1\}))$. Then $I_\ast$ is either $I\cup 1$ or $I\cup 1v$, which proves the ‘if’ part.

Suppose that $x\succeq_{\mathrm{lex}}^{I_j} 2$. Then $1\not\in J\setminus I_j$, so $J\setminus I_j$ cannot have a multiple edge. Thus, $J\setminus I_j$ consists of vertices greater than $\max^{I}(I_j\setminus I)$ by ($\dagger$) in the proof of Lemma 5.1. Then I_j is the first atom of $[I,G]$, which is a contradiction to the assumption.

(2) Suppose $I_j\setminus I=va$ for $v\in V$ and a small edge a of I in $B\cap A$. The existence of a small edge of I implies $\{1,2\}\subset I$ and $v={\min(V\setminus I)}$. Hence, $\prec_{\tiny\text{lex}}^{I}=\prec_{\tiny\text{lex}}^{I_j}$, and they are either

\begin{eqnarray*} &&\prec_{\tiny\text{lex}}^{I}=\prec_{\tiny\text{lex}}^{I_j}: \ 1,2,a_1,a_2,\ldots,a_{k},3, \ldots,n, a_{k+1},\ldots,a_{2m},b_1,\ldots,b_\ell, \quad \text{or}\\ &&\prec_{\tiny\text{lex}}^{I}=\prec_{\tiny\text{lex}}^{I_j}: \ 1,2,a_1,a_2,\ldots,a_{2m},b_1,\ldots,b_{k},3,\ldots,n, b_{k+1},\ldots,b_\ell. \end{eqnarray*}

Suppose $x\prec_{\tiny\text{lex}}^{I_j} \min^{I_j}\{v,b_1\}$. Then $J\setminus I_j$ has an element $a^{\prime}\prec_{\tiny\text{lex}}^{I_j} \min^{I_j}\{v,b_1\}$. Hence, $a^{\prime}\in B\cap A$ and $I_\ast=I \cup aa^{\prime}$, which proves the ‘if’ part.

Suppose $x \succeq_{\mathrm{lex}}^{I_j} \min^{I_j}\{v,b_1\}$. Then $I_j\lessdot J$ is of type (E1ʹ) or (E2). If $J\setminus I_j=b$ for some $b\in B\setminus A$, then $[I,J]$ has only two atoms I_j and $I\cup b$, so I_j is the first. If $J\setminus I_j=cc^{\prime}\subset A$ for some $c,c^{\prime}\succeq_{\mathrm{lex}}^{I_j} v$, then $I_j\setminus I$ consists of the first two smallest elements of $J\setminus I$, so I_j is the first. Then, in any case, I_j is the first atom of $[I,J]$, which is a contradiction to the assumption.

(3) Suppose that $I_j\setminus I$ consists of only big edges of I. Then $I\cap B\neq\emptyset$ and either $I_j\setminus I=aa^{\prime}$ or $I_j\setminus I=b$, where $a,a^{\prime}\in B\cap A$ and $b\in B\setminus A$.

(Case 1) $\underline{I_j\setminus I=aa^{\prime}}$. The existence of a big edge of I in $B\cap A$ implies that $I\cap (B\setminus A)=\emptyset$, so the lexicographic orders $\prec_{\tiny\text{lex}}^{I}$ and $\prec_{\tiny\text{lex}}^{I_j}$ are as follows:

\begin{eqnarray*} \prec_{\tiny\text{lex}}^{I}:&& 1,2,a_1,\ldots,a_{k},3,\ldots,n, a_{k+1},\ldots,a,\ldots,a^{\prime}(=a_t),\ldots, a_{2m},b_{1},\ldots,b_\ell\\ \prec_{\tiny\text{lex}}^{I_j}:&& 1,2,a_1,\ldots,a_{k},\ldots,a,\ldots,a^{\prime}(=a_t),3,\ldots,n, a_{t+1},\ldots, a_{2m},b_{1},\ldots,b_\ell. \end{eqnarray*}

Suppose that $x\preceq_{\tiny\text{lex}}^{I_j} n$. Then $x \prec_{\tiny\text{lex}}^{I} a^{\prime}$ and $I_j\lessdot J$ is of (E2). Hence, we can set $J\setminus I_j=xx^{\prime} \subset A$, where $x\prec_{\tiny\text{lex}}^{I_j}x^{\prime}$. If $x\preceq_{\tiny\text{lex}}^{I_j} {\min(V\setminus I)}$, then $I_\ast=I\cup ax$. If $ {\min(V\setminus I)}\prec_{\tiny\text{lex}}^{I_j} x$, then both x and xʹ are vertices and $I_\ast=I\cup xx^{\prime}$. This proves the ‘if’ part.

Suppose that $x \succ_{\mathrm{lex}}^{I_j} n$. Then either $J\setminus I_j=xx^{\prime}\subset B\cap A$ or $J\setminus I_j=x\in B\setminus A$. Since $a\prec_{\tiny\text{lex}}^{I} a^{\prime} \prec_{\tiny\text{lex}}^{I} x$, I_j is the first atom of $[I,J]$ in $\prec_{\tiny\text{atm}}^{I}$. This is a contradiction to the assumption.

(Case 2) $\underline{I_j\setminus I=b}$. In this case, the lexicographic order $\prec_{\tiny\text{lex}}^{I_j}$ is given as follows:

\begin{equation*}\prec_{\tiny\text{lex}}^{I_j}: 1,2,a_1,a_2,\ldots,a_{2m},b_1,\ldots,b(=b_k),3,4,\ldots,n,b_{k+1},\ldots,b_{\ell}.\end{equation*}

Suppose that $J\setminus I_j$ contains an element x with ${x}\preceq_{\tiny\text{lex}}^{I_j} n$. Note that ${x}\prec_{\tiny\text{lex}}^{I} b$. If x is a vertex, then $J\setminus I_j$ consists of two vertices, and $I_\ast= I\cup (J\setminus I_j)$. Now let x be a multiple edge e. If $e\in B\setminus A$, then $I_\ast=I_j\cup e$. If $e\in B\cap A$, then $J\setminus I_j=ec$ for some $c\in A$, which implies that $I_\ast=I\cup ec$. This proves the ‘if’ part.

If $x \succeq_{\mathrm{lex}}^{I_j} n$, then $J\setminus I_j=\{b^{\prime}\}$ for some $b^{\prime}\in B\setminus A$ with $b\prec_{\tiny\text{lex}}^{I_j} b^{\prime}$, and hence $[I,J]$ has only two atoms I_j and $I\cup b^{\prime}$, where I_j is the first atom in $\prec_{\tiny\text{atm}}^{I}$. This is a contradiction to the assumption.

In order to show (4) and (5), we need to show the following claim.

Proof of Claim 5.7

From the hypotheses, we need to consider the following four cases ①∼④ in the table below, where $a,a^{\prime}\in B\cap A$ with $a^{\prime}\prec_{\tiny\text{lex}}^{I} a$, $b\in B\setminus A$, and $v=\min(V\setminus I)$:

Note that cases ① and ② occur only when $\{1,2\}\subset A$. Let $v_\ast:={\min(V\setminus I_j)}$, provided $V\setminus I_j\neq\emptyset$. In cases ①∼④, if $v_\ast\in J\setminus I_j$, then $I_\ast$’s are $I\cup 1v_\ast$, $I\cup 1v_\ast$, $I\cup vv_\ast$ and $I\cup a^{\prime}v_\ast$, respectively. Note that when $v_{\ast}\not\in J\setminus I_j$, it holds that $x\preceq_{\tiny\text{lex}}^{I_j} v_\ast$ if and only if $x\prec_{\tiny\text{lex}}^{I_j}\max^{I_j}(I_j\setminus I)$. Now we assume that $v_{\ast}\not\in J\setminus I_j$ and $x\prec_{\tiny\text{lex}}^{I_j}\max^{I_j}(I_j\setminus I)$. Since x is a small edge of I_j, x is also a multiple edge, and hence $J\setminus I_j$ consists of multiple edges. In case ②, $I_\ast=I\cup 12 \cup(J\setminus I_j)$. For the other cases, $x\prec_{\tiny\text{lex}}^{I}a$ and $x,a\in B\cap A$. Hence, $I_\ast$ is obtained from I_j by replacing a with x. This proves the ‘if’ part.

To prove the ‘only if’ part, first suppose that $V\setminus I_j\neq\emptyset$ and $x\succ_{\mathrm{lex}}^{I_j}v_\ast$. Then x is either a vertex greater than $v_\ast$ or a big edge of I_j. Hence, $J\setminus I_j$ consists of either two vertices greater than $v_\ast$ or only big edges of I_j. Note that a big edge of I_j is also a big edge of I. Then I_j is the first atom of $[I,J]$ in $\prec_{\tiny\text{atm}}^{I}$, which is a contradiction to the assumption. If $V\setminus I_j=\emptyset$ and $x\succ_{\mathrm{lex}}^{I_j}\max^{I_j}(I_j\setminus I)$, then x is a big edge of I_j, and hence $I_j\setminus I$ consists of only big edges of I_j. Then I_j is the first atom of $[I,J]$ in $\prec_{\tiny\text{atm}}^{I}$, which is a contradiction to the assumption.

From Claim 5.7, (4) follows and (5) partially follows. We exclude the cases of (1)–(4) and the case shown by Claim 5.7. We divide the remaining part into two cases according to the existence of a big edge of I in $I_j\setminus I$.

(Case 1) $\underline{I_j\setminus I}$ has no big edge of I. By excluding (1) and (2), we get one of the following:

• ① $I_j\setminus I=b$, where $b\in B\setminus A$ and b is a small edge of I;

• ② $I_j\setminus I=aa^{\prime}$, where both $a,a^{\prime}\in B\cap A$ are small edges of I; or

• ③ $I_j\setminus I=vv^{\prime}$, where $v, v^{\prime}\in V\setminus\{1,2\}$.

In each case, the ‘only if’ part easily follows, that is, if $x\succ_{\mathrm{lex}}^{I_j} \max^{I_j}(I_j\setminus I)$, then $I_j\setminus I$ has the first $|I_j\setminus I|$ smallest elements of $J\setminus I$ (in $\prec_{\tiny\text{lex}}^{I}$), so I_j is the first atom of $[I,J]$ in $\prec_{\tiny\text{atm}}^{I}$. Let us prove the ‘if’ part of each case. We assume that $x \prec_{\tiny\text{lex}}^{I_j} \max^{I_j}(I_j\setminus I)$ and note that $\prec_{\tiny\text{lex}}^{I}=\prec_{\tiny\text{lex}}^{I_j}$.

① From the existence of a small edge in $B\setminus A$, it follows that $I\cap(B\setminus A)\neq\emptyset$ and

\begin{equation*}\prec_{\tiny\text{lex}}^{I}=\prec_{\tiny\text{lex}}^{I_j}: 1,2,a_1,a_2,\ldots,a_{2m},b_1,\ldots,b,\ldots,b_k,3,\ldots,n,b_{k+1},\ldots,b_{\ell}.\end{equation*}

If $x\prec_{\tiny\text{lex}}^{I_j} b$, then $I_\ast=I\cup (J\setminus I_j)$.

② Assume $a \prec_{\tiny\text{lex}}^{I_j} a^{\prime}$. Then $a^{\prime}=\max^{I_j}(J\setminus I_j)$. The assumption $x\prec_{\tiny\text{lex}}^{I_j} a^{\prime}$ implies that $J\setminus I$ contains a multiple edge a ^ʹʹ with $a^{\prime\prime}\prec_{\tiny\text{lex}}^{I} a^{\prime}$, so $I_\ast= I\cup aa^{\prime\prime}$.

③ Assume $v \prec_{\tiny\text{lex}}^{I_j} v^{\prime}$. Then $v^{\prime}=\max^{I_j}(I_j\setminus I)$, so $x\prec_{\tiny\text{lex}}^{I_j} v^{\prime}$. If $J\setminus I_j \subset V$, then $J\setminus I \subset V$ and $I_\ast=I\cup xy$, where x and y are the first two smallest elements of $J\setminus I$. When $J\setminus I_j \not\subset V$, Table 2 shows how to obtain $I_{\ast}$:

Table 2. $I_\ast$, where $b\in B\setminus A, a,a^{\prime}\in A\cap B, v^{\prime\prime}=\min V\setminus(I_j \cup x)$, $v_\ast=\min\{v,v^{\prime\prime}\}$ and $c_\ast=\min_{I_j}\{v,c\}$

(Case 2) $\underline{I_j\setminus I}$ has a big edge of I. Excluding (3) and (4), we get the following five cases ①∼⑤ in the table, where $w\in \{1,2\}, a,a^{\prime}\in B\cap A$ with $a^{\prime} \prec_{\tiny\text{lex}}^{I_j} a$, $b\in B\setminus A$, and $v=\min(V\setminus (I\cup\{1,2\}))$:

Note that, in any case, the lexicographic ordering $\prec_{\tiny\text{lex}}^{I}$ on $V\cup B$ is given by

\begin{equation*}\prec_{\tiny\text{lex}}^{I}: \ 1,2,3,\ldots,{n},a_1,\ldots,\ldots,a_{2m},b_1,\ldots,b_\ell,\end{equation*}

and any atom of $[I,J]$ containing the element w has a multiple edge. If $x\succ_{\mathrm{lex}}^{I_j}\max^{I_j}(I_j\setminus I)$, then $J\setminus I_j$ cannot have a multiple edge less than $\max^I(B\cap(I_j\setminus I))$ in $\prec_{\tiny\text{lex}}^{I}$. Then I_j is the first atom of $[I,J]$ in $\prec_{\tiny\text{atm}}^{I}$, which is a contradiction to the assumption.

Lemmas 5.5 and 5.6 imply that the ordering $\prec^I_{\mathrm{atm}}$ satisfies Definition 2.3. This proves Theorem 5.4.