<figure><img src="image_1.png" /></figure>

HAL
open science

# The 3-forced 2-structures

Abderrahim Boussaïri, Pierre Ille

► To cite this version:

Abderrahim Boussaïri, Pierre Ille. The 3-forced 2-structures. Discrete Mathematics, Algorithms and Applications, 2023, 10.1142/S1793830923500866. hal-04541269

HAL Id: hal-04541269

https://hal.science/hal-04541269

Submitted on 10 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The 3-forced 2-structures

Abderrahim Boussaïri, Pierre Ille

► To cite this version:

Abderrahim Boussaïri, Pierre Ille. The 3-forced 2-structures. Discrete Mathematics, Algorithms and Applications, 2023, 10.1142/S1793830923500866. hal-04541269

HAL Id: hal-04541269

https://hal.science/hal-04541269v1

Submitted on 10 Apr 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# The 3-forced 2-structures

Abderrahim Boussaïri*† Pierre Ille‡§¶

September 14, 2023

## Abstract

Given sets $S$ and $S'$, a labeled 2-structure is a function $\sigma$ from $(S \times S) \setminus \{(s, s) : s \in S\}$ to $S'$. The set $S$ is called the vertex set of $\sigma$ and denoted by $V(\sigma)$. The label set of $\sigma$ is the set $L(\sigma)$ of $l \in S'$ such that $l = \sigma(v, w)$ for some $v, w \in V(\sigma)$. Given $W \subseteq V(\sigma)$, the 2-substructure $\sigma_{\{l(W \times W) \setminus \{(s,s):s \in W\}\}}$ of $\sigma$ is denoted by $\sigma[W]$. The dual $\sigma^*$ of $\sigma$ is defined on $V(\sigma^*) = V(\sigma)$ as follows. For distinct $v, w \in V(\sigma^*)$, $\sigma^*(v, w) = \sigma(w, v)$. A labeled 2-structure $\sigma$ is reversible provided that for $x, x', y, y' \in S$ such that $x \neq y$ and $x' \neq y'$, if $\sigma(x, y) = \sigma(x', y')$, then $\sigma(y, x) = \sigma(y', x')$. We only consider reversible labeled 2-structures whose vertex set is finite.

Let $\sigma$ and $\tau$ be 2-structures such that $V(\sigma) = V(\tau)$. Given $2 \le k \le |V(\sigma)|$, $\sigma$ and $\tau$ are $k$-hemimorphic if for every $W \subseteq V(\sigma)$ such that $|W| \le k$, $\sigma[W]$ is isomorphic to $\tau[W]$ or $(\tau[W])^*$. Furthermore, let $\sigma$ be a 2-structure. Given $2 \le k \le |V(\sigma)|$, $\sigma$ is $k$-forced if $\sigma$ and $\sigma^*$ are the only 2-structures $k$-hemimorphic to $\sigma$. We characterize the 3-forced 2-structures. Lastly, we provide a large class of 4-forced 2-structures.

**Mathematics Subject Classifications (2010):** 2-structure, $k$-hemimorphy, $k$-forcing.

**Key words:** 05C20, 05C75, 05C76.

## 1 Introduction

Given a digraph $D$, the dual $D^*$ of $D$ is obtained from $D$ by reversing all its arcs. A digraph is self-dual if it is isomorphic to its dual. Consider two digraphs $D$ and $\Delta$ such that $V(D) = V(\Delta)$. Given $2 \le k \le |V(D)|$, we say that $D$ and $\Delta$ are $k$-hemimorphic if for every $W \subseteq V(D)$ such that $|W| \le k$, $D[W]$ is isomorphic to $\Delta[W]$ or $(\Delta[W])^*$. Furthermore, let $D$ be a digraph. Given $2 \le k \le |V(D)|$, $D$ is $k$-forced if $D$ and $D^*$ are the only digraphs $k$-hemimorphic to $D$.

<footnote>*Laboratoire de Mathématiques Fondamentales et Appliquées, Faculté des Sciences Aïn Chock, Hassan II University of Casablanca, Morocco</footnote>

<footnote>†aboussairi@hotmail.com</footnote>

<footnote>‡Aix Marseille Univ, CNRS, I2M, Marseille, France</footnote>

<footnote>§pierre.ille@univ-amu.fr</footnote>

<footnote>¶Corresponding author</footnote>
# The 3-forced 2-structures

Abderrahim Boussaïri*† Pierre Ille‡§¶

September 14, 2023

## Abstract

Given sets $S$ and $S'$, a labeled 2-structure is a function $\sigma$ from $(S \times S) \setminus \{(s, s) : s \in S\}$ to $S'$. The set $S$ is called the vertex set of $\sigma$ and denoted by $V(\sigma)$. The label set of $\sigma$ is the set $L(\sigma)$ of $l \in S'$ such that $l = \sigma(v, w)$ for some $v, w \in V(\sigma)$. Given $W \subseteq V(\sigma)$, the 2-substructure $\sigma_{\{l(W \times W) \setminus \{(s,s):s \in W\}\}}$ of $\sigma$ is denoted by $\sigma[W]$. The dual $\sigma^*$ of $\sigma$ is defined on $V(\sigma^*) = V(\sigma)$ as follows. For distinct $v, w \in V(\sigma^*)$, $\sigma^*(v, w) = \sigma(w, v)$. A labeled 2-structure $\sigma$ is reversible provided that for $x, x', y, y' \in S$ such that $x \neq y$ and $x' \neq y'$, if $\sigma(x, y) = \sigma(x', y')$, then $\sigma(y, x) = \sigma(y', x')$. We only consider reversible labeled 2-structures whose vertex set is finite.

Let $\sigma$ and $\tau$ be 2-structures such that $V(\sigma) = V(\tau)$. Given $2 \le k \le |V(\sigma)|$, $\sigma$ and $\tau$ are $k$-hemimorphic if for every $W \subseteq V(\sigma)$ such that $|W| \le k$, $\sigma[W]$ is isomorphic to $\tau[W]$ or $(\tau[W])^*$. Furthermore, let $\sigma$ be a 2-structure. Given $2 \le k \le |V(\sigma)|$, $\sigma$ is $k$-forced if $\sigma$ and $\sigma^*$ are the only 2-structures $k$-hemimorphic to $\sigma$. We characterize the 3-forced 2-structures. Lastly, we provide a large class of 4-forced 2-structures.

**Mathematics Subject Classifications (2010):** 2-structure, $k$-hemimorphy, $k$-forcing.

**Key words:** 05C20, 05C75, 05C76.

## 1 Introduction

Given a digraph $D$, the dual $D^*$ of $D$ is obtained from $D$ by reversing all its arcs. A digraph is self-dual if it is isomorphic to its dual. Consider two digraphs $D$ and $\Delta$ such that $V(D) = V(\Delta)$. Given $2 \le k \le |V(D)|$, we say that $D$ and $\Delta$ are $k$-hemimorphic if for every $W \subseteq V(D)$ such that $|W| \le k$, $D[W]$ is isomorphic to $\Delta[W]$ or $(\Delta[W])^*$. Furthermore, let $D$ be a digraph. Given $2 \le k \le |V(D)|$, $D$ is $k$-forced if $D$ and $D^*$ are the only digraphs $k$-hemimorphic to $D$.

<footnote>*Laboratoire de Mathématiques Fondamentales et Appliquées, Faculté des Sciences Aïn Chock, Hassan II University of Casablanca, Morocco</footnote>

<footnote>†aboussairi@hotmail.com</footnote>

<footnote>‡Aix Marseille Univ, CNRS, I2M, Marseille, France</footnote>

<footnote>§pierre.ille@univ-amu.fr</footnote>

<footnote>¶Corresponding author</footnote>
Given a digraph $D$, a subset $M$ of $V(D)$ is a module of $D$ if for any $x, y \in M$ and $v \in V(D) \setminus M$, we have

$$xv \in A(D) \iff yv \in A(D)$$

and

$$vx \in A(D) \iff vy \in A(D).$$

For instance, $\emptyset, \{v\}$ ($v \in V(D)$), and $V(D)$ are modules of $D$, called trivial modules of $D$. A digraph $D$ is said to be prime if $|V(D)| \ge 3$ and all its modules are trivial.

Gallai [8, 13] proved that prime partial orders are 3-forced. Afterward, Boussaïri et al. [4, 5] established that prime tournaments are 3-forced as well. In general, a prime digraph is not 3-forced. But, a prime digraph becomes 3-forced if all its prime subdigraphs of size 3 are self-dual. We denote by $F$ the digraph $(\{0, 1, 2\}, \{01, 10, 12\})$. The only prime digraphs of size 3 that are not self-dual are $F$ and $F^*$. They are called the flags (see Definition 31). Boussaïri et al. [4, 5] proved that prime digraphs without flags are 3-forced. Boussaïri [2] characterized the 3-forced prime digraphs. This result was published in [3]. Lastly, given a digraph $D$, the set of the unordered pairs $\{v, w\}$ of vertices of $D$ such that $|\{vw, wv\}| \cap A(D)| = 1$ is denoted by $O(D)$. Boussaïri [2] proved that a prime digraph $D$ such that the graph $(V(D), O(D))$ is connected is 4-forced. Dammak obtained this result as an easy consequence of the main results proved in [6].

Our purpose is to extend the characterization of 3-forced digraphs (see Theorem 8) and the result on 4-forced digraphs above (see Theorem 10) to reversible labeled 2-structures.

Given sets $S$ and $S'$, a labeled 2-structure is a function $\sigma$ from $(S \times S) \setminus \{(s, s) : s \in S\}$ to $S'$. The set $S$ is called the vertex set of $\sigma$ and denoted by $V(\sigma)$. The label set of $\sigma$ is the set $L(\sigma)$ of $l \in S'$ such that $l = \sigma(v, w)$ for some $v, w \in V(\sigma)$. A labeled 2-structure $\sigma$ is reversible [7] provided that for $x, x', y, y' \in S$ such that $x \neq y$ and $x' \neq y'$, we have

$$\text{if } \sigma(x, y) = \sigma(x', y'), \text{ then } \sigma(y, x) = \sigma(y', x'). \qquad (1)$$

In what follows, we only consider reversible labeled 2-structures whose vertex set is finite. Given such a 2-structure $\sigma$, set $v(\sigma) = |V(\sigma)|$.

For instance, we associate with a digraph $D$ the 2-structure $\sigma_D$ defined on $V(\sigma_D) = V(D)$ with $L(\sigma_D) \subseteq \mathbb{Z}_4$ as follows. For any $v, w \in V(\sigma_D)$ such that $v \neq w$,

$$\sigma_D(v, w) = \begin{cases} 0 & \text{if } vw, wv \notin A(D), \\ 2 & \text{if } vw, wv \in A(D), \\ 1 & \text{if } vw \in A(D) \text{ and } wv \notin A(D), \\ 3 & \text{if } wv \in A(D) \text{ and } vw \notin A(D). \end{cases}$$

Hence, given distinct $v, w \in V(\sigma_D)$, we have $\sigma_D(v, w) = -\sigma_D(w, v) \pmod 4$.
Given a digraph $D$, a subset $M$ of $V(D)$ is a module of $D$ if for any $x, y \in M$ and $v \in V(D) \setminus M$, we have

$$xv \in A(D) \iff yv \in A(D)$$

and

$$vx \in A(D) \iff vy \in A(D).$$

For instance, $\emptyset, \{v\}$ ($v \in V(D)$), and $V(D)$ are modules of $D$, called trivial modules of $D$. A digraph $D$ is said to be prime if $|V(D)| \ge 3$ and all its modules are trivial.

Gallai [8, 13] proved that prime partial orders are 3-forced. Afterward, Boussaïri et al. [4, 5] established that prime tournaments are 3-forced as well. In general, a prime digraph is not 3-forced. But, a prime digraph becomes 3-forced if all its prime subdigraphs of size 3 are self-dual. We denote by $F$ the digraph $(\{0, 1, 2\}, \{01, 10, 12\})$. The only prime digraphs of size 3 that are not self-dual are $F$ and $F^*$. They are called the flags (see Definition 31). Boussaïri et al. [4, 5] proved that prime digraphs without flags are 3-forced. Boussaïri [2] characterized the 3-forced prime digraphs. This result was published in [3]. Lastly, given a digraph $D$, the set of the unordered pairs $\{v, w\}$ of vertices of $D$ such that $|\{vw, wv\}| \cap A(D)| = 1$ is denoted by $O(D)$. Boussaïri [2] proved that a prime digraph $D$ such that the graph $(V(D), O(D))$ is connected is 4-forced. Dammak obtained this result as an easy consequence of the main results proved in [6].

Our purpose is to extend the characterization of 3-forced digraphs (see Theorem 8) and the result on 4-forced digraphs above (see Theorem 10) to reversible labeled 2-structures.

Given sets $S$ and $S'$, a labeled 2-structure is a function $\sigma$ from $(S \times S) \setminus \{(s, s) : s \in S\}$ to $S'$. The set $S$ is called the vertex set of $\sigma$ and denoted by $V(\sigma)$. The label set of $\sigma$ is the set $L(\sigma)$ of $l \in S'$ such that $l = \sigma(v, w)$ for some $v, w \in V(\sigma)$. A labeled 2-structure $\sigma$ is reversible [7] provided that for $x, x', y, y' \in S$ such that $x \neq y$ and $x' \neq y'$, we have

$$\text{if } \sigma(x, y) = \sigma(x', y'), \text{ then } \sigma(y, x) = \sigma(y', x'). \qquad (1)$$

In what follows, we only consider reversible labeled 2-structures whose vertex set is finite. Given such a 2-structure $\sigma$, set $v(\sigma) = |V(\sigma)|$.

For instance, we associate with a digraph $D$ the 2-structure $\sigma_D$ defined on $V(\sigma_D) = V(D)$ with $L(\sigma_D) \subseteq \mathbb{Z}_4$ as follows. For any $v, w \in V(\sigma_D)$ such that $v \neq w$,

$$\sigma_D(v, w) = \begin{cases} 0 & \text{if } vw, wv \notin A(D), \\ 2 & \text{if } vw, wv \in A(D), \\ 1 & \text{if } vw \in A(D) \text{ and } wv \notin A(D), \\ 3 & \text{if } wv \in A(D) \text{ and } vw \notin A(D). \end{cases}$$

Hence, given distinct $v, w \in V(\sigma_D)$, we have $\sigma_D(v, w) = -\sigma_D(w, v) \pmod 4$.
Let $\sigma$ be a 2-structure. With each $W \subseteq V(\sigma)$, we associate the 2-substructure $\sigma[W]$ of $\sigma$ induced by $W$ defined by

$$ \sigma[W] = \sigma_{\uparrow(W \times W)} \setminus \{(w, w): w \in W\}. $$

When $W = V(\sigma) \setminus W'$, $\sigma[W]$ is also denoted by $\sigma - W'$, and by $\sigma - w$ when $W' = \{w\}$.

## 1.1 Definitions and notations

**Definition 1.** A 2-structure $\sigma$ is constant if $|L(\sigma)| = 1$. A 2-structure $\sigma$ is linear if there exist distinct $l, l' \in L(\sigma)$ such that $(V(\sigma), \sigma^{-1}(l))$ and $(V(\sigma), \sigma^{-1}(l'))$ are linear orders (in this case, we obtain $L(\sigma) = \{l, l'\}$ and $(V(\sigma), \sigma^{-1}(l')) = (V(\sigma), \sigma^{-1}(l'))^*$).

Let $\sigma$ be a 2-structure. Set

$$ \tilde{L}(\sigma) = \{\{\sigma(v, w), \sigma(w, v)\} : \{v, w\} \in \binom{V(\sigma)}{2}\}. $$

Let $p, q \in \tilde{L}(\sigma)$. By (1), we have $p = q$ or $p \cap q = \emptyset$. We consider the function

$$ \tilde{\sigma} : \binom{V(\sigma)}{2} \longrightarrow \tilde{L}(\sigma) \\ \{v, w\} \longmapsto \{\sigma(v, w), \sigma(w, v)\}. $$

For each $i = 1$ or 2, set

$$ \tilde{L}_i(\sigma) = \{p \in \tilde{L}(\sigma) : |p| = i\}. $$

Furthermore, set

$$ E_i(\sigma) = \{\{v, w\} \in \binom{V(\sigma)}{2} : \tilde{\sigma}(\{v, w\}) \in \tilde{L}_i(\sigma)\}. $$

We consider the graph $G_\sigma$ defined on $V(G_\sigma) = \tilde{L}_2(\sigma)$ in the following manner. For any $p, q \in V(G_\sigma)$ such that $p \neq q$, $pq \in E(G_\sigma)$ if there exists $W \subseteq V(\sigma)$ satisfying $|W| = 3$, $\sigma[W]$ is prime, and $p, q \in \tilde{L}(\sigma[W])$. For a digraph $D$, the edge set of $G_{\sigma_D}$ is empty because $|\tilde{L}_2(\sigma_D)| \le 1$.

We associate with a 2-structure $\sigma$ the 2-structure $\vec{\sigma}$ defined on $V(\vec{\sigma}) = V(\sigma)$ as follows. If $|\tilde{L}_1(\sigma)| \le 1$, then $\vec{\sigma} = \sigma$. Now, suppose that $|\tilde{L}_1(\sigma)| \ge 2$. Choose $l \in L(\sigma)$ such that $\{l\} \in \tilde{L}_1(\sigma)$. For any $v, w \in V(\sigma)$ such that $v \neq w$,

$$ \vec{\sigma}(v, w) = \begin{cases} \sigma(v, w) & \text{if } \{v, w\} \in E_2(\sigma), \\ l & \text{if } \{v, w\} \in E_1(\sigma). \end{cases} $$

For instance, consider a digraph $D$ such that there exist $v, v', w, w' \in V(D)$ satisfying $v \neq w, v' \neq w', vw, wv \in A(D)$, and $v'w', w'v' \notin A(D)$. We obtain $\tilde{L}_1(\sigma_D) = \{\{0\}, \{2\}\}$. Now, choose $l = 0$. Consider the oriented graph $\vec{D}$ defined
Let $\sigma$ be a 2-structure. With each $W \subseteq V(\sigma)$, we associate the 2-substructure $\sigma[W]$ of $\sigma$ induced by $W$ defined by

$$ \sigma[W] = \sigma_{\uparrow(W \times W)} \setminus \{(w, w): w \in W\}. $$

When $W = V(\sigma) \setminus W'$, $\sigma[W]$ is also denoted by $\sigma - W'$, and by $\sigma - w$ when $W' = \{w\}$.

## 1.1 Definitions and notations

**Definition 1.** A 2-structure $\sigma$ is constant if $|L(\sigma)| = 1$. A 2-structure $\sigma$ is linear if there exist distinct $l, l' \in L(\sigma)$ such that $(V(\sigma), \sigma^{-1}(l))$ and $(V(\sigma), \sigma^{-1}(l'))$ are linear orders (in this case, we obtain $L(\sigma) = \{l, l'\}$ and $(V(\sigma), \sigma^{-1}(l')) = (V(\sigma), \sigma^{-1}(l'))^*$).

Let $\sigma$ be a 2-structure. Set

$$ \tilde{L}(\sigma) = \{\{\sigma(v, w), \sigma(w, v)\} : \{v, w\} \in \binom{V(\sigma)}{2}\}. $$

Let $p, q \in \tilde{L}(\sigma)$. By (1), we have $p = q$ or $p \cap q = \emptyset$. We consider the function

$$ \tilde{\sigma} : \binom{V(\sigma)}{2} \longrightarrow \tilde{L}(\sigma) \\ \{v, w\} \longmapsto \{\sigma(v, w), \sigma(w, v)\}. $$

For each $i = 1$ or 2, set

$$ \tilde{L}_i(\sigma) = \{p \in \tilde{L}(\sigma) : |p| = i\}. $$

Furthermore, set

$$ E_i(\sigma) = \{\{v, w\} \in \binom{V(\sigma)}{2} : \tilde{\sigma}(\{v, w\}) \in \tilde{L}_i(\sigma)\}. $$

We consider the graph $G_\sigma$ defined on $V(G_\sigma) = \tilde{L}_2(\sigma)$ in the following manner. For any $p, q \in V(G_\sigma)$ such that $p \neq q$, $pq \in E(G_\sigma)$ if there exists $W \subseteq V(\sigma)$ satisfying $|W| = 3$, $\sigma[W]$ is prime, and $p, q \in \tilde{L}(\sigma[W])$. For a digraph $D$, the edge set of $G_{\sigma_D}$ is empty because $|\tilde{L}_2(\sigma_D)| \le 1$.

We associate with a 2-structure $\sigma$ the 2-structure $\vec{\sigma}$ defined on $V(\vec{\sigma}) = V(\sigma)$ as follows. If $|\tilde{L}_1(\sigma)| \le 1$, then $\vec{\sigma} = \sigma$. Now, suppose that $|\tilde{L}_1(\sigma)| \ge 2$. Choose $l \in L(\sigma)$ such that $\{l\} \in \tilde{L}_1(\sigma)$. For any $v, w \in V(\sigma)$ such that $v \neq w$,

$$ \vec{\sigma}(v, w) = \begin{cases} \sigma(v, w) & \text{if } \{v, w\} \in E_2(\sigma), \\ l & \text{if } \{v, w\} \in E_1(\sigma). \end{cases} $$

For instance, consider a digraph $D$ such that there exist $v, v', w, w' \in V(D)$ satisfying $v \neq w, v' \neq w', vw, wv \in A(D)$, and $v'w', w'v' \notin A(D)$. We obtain $\tilde{L}_1(\sigma_D) = \{\{0\}, \{2\}\}$. Now, choose $l = 0$. Consider the oriented graph $\vec{D}$ defined
on $V(\vec{D}) = V(D)$ by $A(\vec{D}) = A(D) \setminus A(D^*)$, where $D^*$ is the dual of $D$ defined on $V(D^*) = V(D)$ by $A(D^*) = \{vw : wv \in A(D)\}$. We obtain

$$ (\overrightarrow{\sigma_D}) = \sigma_{\vec{D}}. $$

Later, in Convention 26, we set out the choice of the label “l” when we consider several 2-structures sharing the same label set.

**Definition 2.** We associate with a 2-structure $\sigma$ its dual $\sigma^*$ defined on $V(\sigma^*) = V(\sigma)$ as follows. For any $v, w \in V(\sigma^*)$ such that $v \neq w$, $\sigma^*(v, w) = \sigma(w, v)$.

Consider 2-structures $\sigma$ and $\tau$ such that $V(\sigma) = V(\tau)$. Given $2 \le k \le v(\sigma)$, we say that $\sigma$ and $\tau$ are k-hemimorphic if for every $W \subseteq V(\sigma)$ such that $|W| \le k$, $\sigma[W]$ is isomorphic to $\tau[W]$ or $(\tau[W])^*$.

Given $2 \le k \le v(\sigma)$, a 2-structure $\sigma$ is k-forced if $\sigma$ and $\sigma^*$ are the only 2-structures that are k-hemimorphic to $\sigma$.

**Remark 3.** For a digraph $D$, we obtain $(\sigma_D)^* = \sigma_{(D^*)}$. Consider digraphs $D$ and $\Delta$ such that $V(D) = V(\Delta)$. Given $2 \le k \le |V(D)|$, it follows that two digraphs $D$ and $\Delta$ are k-hemimorphic if and only if $\sigma_D$ and $\sigma_\Delta$ are k-hemimorphic. Let $D$ be a digraph. Given $2 \le k \le |V(D)|$, we obtain that $D$ is k-forced if and only $\sigma_D$ is.

## 1.2 Modular decomposition

For this section, we refer to [8, 13] for graphs, [5] for digraphs, [10] for binary structures, and [7, 11] for 2-structures.

Let $\sigma$ be a 2-structure. A subset $M$ of $V(\sigma)$ is a module of $\sigma$ if for any $x, y \in M$ and $v \in V(\sigma) \setminus M$, we have $\sigma(x, v) = \sigma(y, v)$. For instance, $\emptyset$, $V(\sigma)$ and $\{v\}$ ($v \in V(\sigma)$) are modules of $\sigma$, called the trivial modules of $\sigma$. A 2-structure $\sigma$ is indecomposable if all its modules are trivial, otherwise it is decomposable. A 2-structure $\sigma$ is prime if it is indecomposable with $v(\sigma) \ge 3$.

Let $\sigma$ be a 2-structure. For disjoint modules $M$ and $N$ of $\sigma$, we have $\sigma(x, y) = \sigma(x', y')$ for any $x, x' \in M$ and $y, y' \in N$. This property allows us to define the quotient as follows. A modular partition of $\sigma$ is a partition of $V(\sigma)$ in modules of $\sigma$. With a modular partition $P$ of $\sigma$, we associate the quotient of $\sigma$ by $P$ defined on $V(\sigma/P) = P$ as follows. For distinct $X, Y \in P$, $(\sigma/P)(X, Y) = \sigma(x, y)$, where $x \in X$ and $y \in Y$.

Let $\sigma$ be a 2-structure. A subset $M$ of $V(\sigma)$ is a strong module of $\sigma$ if $M$ is a module of $\sigma$ satisfying: for every module $N$ of $\sigma$, if $M \cap N \neq \emptyset$, then $M \subseteq N$ or $N \subseteq M$. For instance, the trivial modules of $\sigma$ are strong modules too. We denote by $\mathcal{G}(\sigma)$ the family of the strong modules of $\sigma$ which are maximal under inclusion among the proper strong modules of $\sigma$. Gallai's decomposition theorem follows.

**Theorem 4.** Given a 2-structure $\sigma$ such that $v(\sigma) \ge 2$, $\mathcal{G}(\sigma)$ is a modular partition of $\sigma$, and the quotient $\sigma/\mathcal{G}(\sigma)$ is constant, linear, or prime.
on $V(\vec{D}) = V(D)$ by $A(\vec{D}) = A(D) \setminus A(D^*)$, where $D^*$ is the dual of $D$ defined on $V(D^*) = V(D)$ by $A(D^*) = \{vw : wv \in A(D)\}$. We obtain

$$ (\overrightarrow{\sigma_D}) = \sigma_{\vec{D}}. $$

Later, in Convention 26, we set out the choice of the label “l” when we consider several 2-structures sharing the same label set.

**Definition 2.** We associate with a 2-structure $\sigma$ its dual $\sigma^*$ defined on $V(\sigma^*) = V(\sigma)$ as follows. For any $v, w \in V(\sigma^*)$ such that $v \neq w$, $\sigma^*(v, w) = \sigma(w, v)$.

Consider 2-structures $\sigma$ and $\tau$ such that $V(\sigma) = V(\tau)$. Given $2 \le k \le v(\sigma)$, we say that $\sigma$ and $\tau$ are k-hemimorphic if for every $W \subseteq V(\sigma)$ such that $|W| \le k$, $\sigma[W]$ is isomorphic to $\tau[W]$ or $(\tau[W])^*$.

Given $2 \le k \le v(\sigma)$, a 2-structure $\sigma$ is k-forced if $\sigma$ and $\sigma^*$ are the only 2-structures that are k-hemimorphic to $\sigma$.

**Remark 3.** For a digraph $D$, we obtain $(\sigma_D)^* = \sigma_{(D^*)}$. Consider digraphs $D$ and $\Delta$ such that $V(D) = V(\Delta)$. Given $2 \le k \le |V(D)|$, it follows that two digraphs $D$ and $\Delta$ are k-hemimorphic if and only if $\sigma_D$ and $\sigma_\Delta$ are k-hemimorphic. Let $D$ be a digraph. Given $2 \le k \le |V(D)|$, we obtain that $D$ is k-forced if and only $\sigma_D$ is.

## 1.2 Modular decomposition

For this section, we refer to [8, 13] for graphs, [5] for digraphs, [10] for binary structures, and [7, 11] for 2-structures.

Let $\sigma$ be a 2-structure. A subset $M$ of $V(\sigma)$ is a module of $\sigma$ if for any $x, y \in M$ and $v \in V(\sigma) \setminus M$, we have $\sigma(x, v) = \sigma(y, v)$. For instance, $\emptyset$, $V(\sigma)$ and $\{v\}$ ($v \in V(\sigma)$) are modules of $\sigma$, called the trivial modules of $\sigma$. A 2-structure $\sigma$ is indecomposable if all its modules are trivial, otherwise it is decomposable. A 2-structure $\sigma$ is prime if it is indecomposable with $v(\sigma) \ge 3$.

Let $\sigma$ be a 2-structure. For disjoint modules $M$ and $N$ of $\sigma$, we have $\sigma(x, y) = \sigma(x', y')$ for any $x, x' \in M$ and $y, y' \in N$. This property allows us to define the quotient as follows. A modular partition of $\sigma$ is a partition of $V(\sigma)$ in modules of $\sigma$. With a modular partition $P$ of $\sigma$, we associate the quotient of $\sigma$ by $P$ defined on $V(\sigma/P) = P$ as follows. For distinct $X, Y \in P$, $(\sigma/P)(X, Y) = \sigma(x, y)$, where $x \in X$ and $y \in Y$.

Let $\sigma$ be a 2-structure. A subset $M$ of $V(\sigma)$ is a strong module of $\sigma$ if $M$ is a module of $\sigma$ satisfying: for every module $N$ of $\sigma$, if $M \cap N \neq \emptyset$, then $M \subseteq N$ or $N \subseteq M$. For instance, the trivial modules of $\sigma$ are strong modules too. We denote by $\mathcal{G}(\sigma)$ the family of the strong modules of $\sigma$ which are maximal under inclusion among the proper strong modules of $\sigma$. Gallai's decomposition theorem follows.

**Theorem 4.** Given a 2-structure $\sigma$ such that $v(\sigma) \ge 2$, $\mathcal{G}(\sigma)$ is a modular partition of $\sigma$, and the quotient $\sigma/\mathcal{G}(\sigma)$ is constant, linear, or prime.
## 1.3 The main results

Since it is not difficult to verify the next fact, we omit its proof.

**Fact 5.** Given a 2-structure $\sigma$ such that $(V(\sigma), E_2(\sigma))$ admits an isolated vertex $v$, $\sigma$ is 3-forced if and only if $\sigma - v$ is as well.

In Section 3, we show the next preliminary result.

**Lemma 6.** Given a 2-structure $\sigma$, $\sigma$ is 3-forced if and only if $\vec{\sigma}$ is 3-forced.

**Remark 7.** The next assumption follows from Fact 5 and Lemma 6. To characterize the 2-structures $\sigma$ that are 3-forced, we can assume that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices.

The two main theorems follow.

**Theorem 8.** Let $\sigma$ be a 2-structure. Suppose that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices. The 2-structure $\sigma$ is 3-forced if and only if $\sigma$ satisfies the following three statements

(T1) $G_\sigma$ is connected;

(T2) for each $M \in \mathcal{G}(\sigma)$, $E_2(\sigma[M]) = \emptyset$;

(T3) if $|\mathcal{G}(\sigma)| \ge 3$, then $\sigma/\mathcal{G}(\sigma)$ is prime.

**Remark 9.** Theorem 8 is obtained by Boussaïri [2] for digraphs. Clearly, Statement (T1) is unnecessary for digraphs because it is trivially satisfied. Theorem 8 for digraphs is proved in [3].

**Theorem 10.** Let $\sigma$ be a prime 2-structure. If $(V(\sigma), E_2(\sigma))$ is connected, then $\sigma$ is 4-forced.

# 2 Preliminaries

## 2.1 Prime 2-structures

The next result is classical in the study of prime 2-structures (for instance, see Ehrenfeucht et al. [7]).

**Lemma 11.** Given a prime 2-structure $\sigma$, there exists $X \subseteq V(\sigma)$ such that $|X| = 3$ or 4 and $\sigma[X]$ is prime.

To obtain prime 2-substructure of larger sizes, we use the following subsets.

**Notation 12.** Let $\sigma$ be a 2-structure. Given $X \not\subseteq V(\sigma)$ such that $\sigma[X]$ is prime, consider the following subsets of $V(\sigma) \setminus X$

* $\text{Ext}_\sigma(X)$ denotes the set of $v \in V(\sigma) \setminus X$ such that $\sigma[X \cup \{v\}]$ is prime;

* $\langle X \rangle_\sigma$ denotes the set of $v \in V(\sigma) \setminus X$ such that $X$ is a module of $\sigma[X \cup \{v\}]$;
## 1.3 The main results

Since it is not difficult to verify the next fact, we omit its proof.

**Fact 5.** Given a 2-structure $\sigma$ such that $(V(\sigma), E_2(\sigma))$ admits an isolated vertex $v$, $\sigma$ is 3-forced if and only if $\sigma - v$ is as well.

In Section 3, we show the next preliminary result.

**Lemma 6.** Given a 2-structure $\sigma$, $\sigma$ is 3-forced if and only if $\vec{\sigma}$ is 3-forced.

**Remark 7.** The next assumption follows from Fact 5 and Lemma 6. To characterize the 2-structures $\sigma$ that are 3-forced, we can assume that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices.

The two main theorems follow.

**Theorem 8.** Let $\sigma$ be a 2-structure. Suppose that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices. The 2-structure $\sigma$ is 3-forced if and only if $\sigma$ satisfies the following three statements

(T1) $G_\sigma$ is connected;

(T2) for each $M \in \mathcal{G}(\sigma)$, $E_2(\sigma[M]) = \emptyset$;

(T3) if $|\mathcal{G}(\sigma)| \ge 3$, then $\sigma/\mathcal{G}(\sigma)$ is prime.

**Remark 9.** Theorem 8 is obtained by Boussaïri [2] for digraphs. Clearly, Statement (T1) is unnecessary for digraphs because it is trivially satisfied. Theorem 8 for digraphs is proved in [3].

**Theorem 10.** Let $\sigma$ be a prime 2-structure. If $(V(\sigma), E_2(\sigma))$ is connected, then $\sigma$ is 4-forced.

# 2 Preliminaries

## 2.1 Prime 2-structures

The next result is classical in the study of prime 2-structures (for instance, see Ehrenfeucht et al. [7]).

**Lemma 11.** Given a prime 2-structure $\sigma$, there exists $X \subseteq V(\sigma)$ such that $|X| = 3$ or 4 and $\sigma[X]$ is prime.

To obtain prime 2-substructure of larger sizes, we use the following subsets.

**Notation 12.** Let $\sigma$ be a 2-structure. Given $X \not\subseteq V(\sigma)$ such that $\sigma[X]$ is prime, consider the following subsets of $V(\sigma) \setminus X$

* $\text{Ext}_\sigma(X)$ denotes the set of $v \in V(\sigma) \setminus X$ such that $\sigma[X \cup \{v\}]$ is prime;

* $\langle X \rangle_\sigma$ denotes the set of $v \in V(\sigma) \setminus X$ such that $X$ is a module of $\sigma[X \cup \{v\}]$;
• for each $y \in X$, $X_\sigma(y)$ denotes the set of $v \in V(\sigma) \setminus X$ such that $\{y, v\}$ is a module of $\sigma[X \cup \{v\}]$.

The set $\{\mathrm{Ext}_\sigma(X), \langle X \rangle_\sigma\} \cup \{X_\sigma(y) : y \in X\}$ is denoted by $p_{(\sigma,X)}$.

Using the fact that the family of the modules of a 2-structure is weakly partitive (for instance, see Ille and Woodrow [12]), it is not difficult to verify the following claim.

**Claim 13.** Given a 2-structure $\sigma$, consider $X \subseteq V(\sigma)$ such that $\sigma[X]$ is prime. The set $p_{(\sigma,X)}$ is a partition of $V(\sigma) \setminus X$.

Using the subsets described in Notation 12, Ehrenfeucht et al. [7] obtained the following result (see [7, Theorem 6.5]).

**Proposition 14.** Given a prime 2-structure $\sigma$, consider $X \subseteq V(\sigma)$ such that $\sigma[X]$ is prime. If $|V(\sigma) \setminus X| \ge 2$, then there exist $v, w \in V(\sigma) \setminus X$ such that $v \ne w$ and $\sigma[X \cup \{v, w\}]$ is prime.

The next result is an immediate consequence of Lemma 11 and Proposition 14.

**Corollary 15.** Let $\sigma$ be a prime 2-structure. If $v(\sigma) \ge 5$, then there exists $X \not\subseteq V(\sigma)$ such that $\sigma[X]$ is prime and $|V(\sigma) \setminus X| \le 2$.

The next result follows from Proposition 14.

**Lemma 16.** Given a 2-structure $\sigma$ such that $v(\sigma) \ge 5$, Suppose that there exists $X \not\subseteq V(\sigma)$ such that $\sigma[X]$ is prime. If $\sigma$ is prime, then there exist elements $y_0, \dots, y_{v(\sigma)-|X|-1}$ of $V(\sigma) \setminus X$ fulfilling the next three statements

(S1) $X \cup \{y_0, \dots, y_{v(\sigma)-|X|-1}\} = V(\sigma)$;

(S2) if $\sigma[X \cup \{y_0\}]$ is decomposable, then there exists $z \in X$ such that $\{z, y_0\}$ is a module of $\sigma[X \cup \{y_0\}]$.

(S3) for each $k \in \{1, \dots, v(\sigma) - |X| - 2\}$, if $\sigma[X \cup \{y_0, \dots, y_k\}]$ is decomposable, then the following assertions hold

• $k$ is even,

• $\sigma[X \cup \{y_0, \dots, y_{k-1}\}]$ is prime,

• there exists $z \in X \cup \{y_0, \dots, y_{k-1}\}$ such that $\{z, y_k\}$ is a module of $\sigma[X \cup \{y_0, \dots, y_k\}]$.

In particular, for every $k \in \{0, \dots, v(\sigma) - |X| - 1\}$, $\sigma[X \cup \{y_0, \dots, y_k\}] / \mathcal{G}(\sigma[X \cup \{y_0, \dots, y_k\}])$ is prime.

*Proof.* It suffices to define $y_0$ and $y_1$, and then to pursue by proceeding by induction. By Proposition 14, there exist $v, w \in V(\sigma) \setminus X$ such that $v \ne w$ and $\sigma[X \cup \{v, w\}]$ is prime. If $v, w \in \langle X \rangle_\sigma$ (see Notation 12), then $X$ is a
• for each $y \in X$, $X_\sigma(y)$ denotes the set of $v \in V(\sigma) \setminus X$ such that $\{y, v\}$ is a module of $\sigma[X \cup \{v\}]$.

The set $\{\mathrm{Ext}_\sigma(X), \langle X \rangle_\sigma\} \cup \{X_\sigma(y) : y \in X\}$ is denoted by $p_{(\sigma,X)}$.

Using the fact that the family of the modules of a 2-structure is weakly partitive (for instance, see Ille and Woodrow [12]), it is not difficult to verify the following claim.

**Claim 13.** Given a 2-structure $\sigma$, consider $X \subseteq V(\sigma)$ such that $\sigma[X]$ is prime. The set $p_{(\sigma,X)}$ is a partition of $V(\sigma) \setminus X$.

Using the subsets described in Notation 12, Ehrenfeucht et al. [7] obtained the following result (see [7, Theorem 6.5]).

**Proposition 14.** Given a prime 2-structure $\sigma$, consider $X \subseteq V(\sigma)$ such that $\sigma[X]$ is prime. If $|V(\sigma) \setminus X| \ge 2$, then there exist $v, w \in V(\sigma) \setminus X$ such that $v \ne w$ and $\sigma[X \cup \{v, w\}]$ is prime.

The next result is an immediate consequence of Lemma 11 and Proposition 14.

**Corollary 15.** Let $\sigma$ be a prime 2-structure. If $v(\sigma) \ge 5$, then there exists $X \not\subseteq V(\sigma)$ such that $\sigma[X]$ is prime and $|V(\sigma) \setminus X| \le 2$.

The next result follows from Proposition 14.

**Lemma 16.** Given a 2-structure $\sigma$ such that $v(\sigma) \ge 5$, Suppose that there exists $X \not\subseteq V(\sigma)$ such that $\sigma[X]$ is prime. If $\sigma$ is prime, then there exist elements $y_0, \dots, y_{v(\sigma)-|X|-1}$ of $V(\sigma) \setminus X$ fulfilling the next three statements

$$ (S1) \quad X \cup \{y_0, \dots, y_{v(\sigma)-|X|-1}\} = V(\sigma); $$

$$ (S2) \quad \text{if } \sigma[X \cup \{y_0\}] \text{ is decomposable, then there exists } z \in X \text{ such that } \{z, y_0\} \text{ is a module of } \sigma[X \cup \{y_0\}]. $$

$$ (S3) \quad \text{for each } k \in \{1, \dots, v(\sigma) - |X| - 2\}, \text{ if } \sigma[X \cup \{y_0, \dots, y_k\}] \text{ is decomposable, then the following assertions hold} $$

• $k$ is even,

• $\sigma[X \cup \{y_0, \dots, y_{k-1}\}]$ is prime,

• there exists $z \in X \cup \{y_0, \dots, y_{k-1}\}$ such that $\{z, y_k\}$ is a module of $\sigma[X \cup \{y_0, \dots, y_k\}]$.

In particular, for every $k \in \{0, \dots, v(\sigma) - |X| - 1\}$, $\sigma[X \cup \{y_0, \dots, y_k\}] / \mathscr{G}(\sigma[X \cup \{y_0, \dots, y_k\}])$ is prime.

*Proof.* It suffices to define $y_0$ and $y_1$, and then to pursue by proceeding by induction. By Proposition 14, there exist $v, w \in V(\sigma) \setminus X$ such that $v \ne w$ and $\sigma[X \cup \{v, w\}]$ is prime. If $v, w \in \langle X \rangle_\sigma$ (see Notation 12), then $X$ is a
module of $\sigma[X \cup \{v, w\}]$, which contradicts the fact that $\sigma[X \cup \{v, w\}]$ is prime. Consequently, we have $\{v, w\} \setminus \langle X \rangle_{\sigma} \neq \emptyset$. It follows from Claim 13 that

$$ \{v, w\} \cap (\mathrm{Ext}_{\sigma}(X) \cup (\bigcup_{y \in X} X_{\sigma}(y))) \neq \emptyset. $$

For instance, assume that $v \in \mathrm{Ext}_{\sigma}(X) \cup (\bigcup_{y \in X} X_{\sigma}(y))$. Clearly, for $t \in X_{\sigma}(y)$, where $y \in X$, we have

$$ \begin{gathered} \mathcal{G}(\sigma[X \cup \{t\}]) = \{\{y,t\}\} \cup \{\{z\} : z \in X \setminus \{y\}\} \\ \text{and} \\ \sigma[X \cup \{t\}]/\mathcal{G}(\sigma[X \cup \{t\}]) \text{ is prime.} \end{gathered} $$

Hence, we can choose $y_0 = v$ and $y_1 = w$. $\square$

**Lemma 17.** Given a 2-structure $\sigma$ such that $v(\sigma) \ge 5$, if $\sigma/\mathcal{G}(\sigma)$ is prime, then there exists $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime as well.

*Proof.* The result is obvious when $\sigma$ is decomposable. Hence, suppose that $\sigma$ is prime. By Corollary 15, there exists $X \neq V(\sigma)$ such that $\sigma[X]$ is prime and $|V(\sigma) \setminus X| \le 2$. To conclude, it suffices to apply Lemma 16. $\square$

## 2.2 Critical 2-structures

A prime 2-structure $\sigma$ is critical if for every $v \in V(\sigma)$, $\sigma - v$ is decomposable. Critical digraphs were characterized by Schmerl and Trotter [14] (see also Boud-abbous and Ille [1]).

**Notation 18.** Given $n \ge 2$, we denote by $\Sigma_{2n}$ the sets of the 2-structures $\sigma$ defined on $V(\sigma) = \{0, \dots, 2n-1\}$ such that $|\tilde{L}_2(\sigma)| = 2$, $\tilde{\sigma}(\{0,1\}) \neq \tilde{\sigma}(\{0,2\})$, and for $p, q \in \{0, \dots, 2n-1\}$ such that $p < q$, we have

$$ \sigma(p, q) = \begin{cases} \sigma(0,1) & \text{if } p \text{ is even and } q \text{ is odd,} \\ \sigma(0,2) & \text{otherwise.} \end{cases} \qquad (2) $$

**Claim 19.** Given $n \ge 2$, the elements of $\Sigma_{2n}$ are critical 2-structures.

*Proof.* To begin, we prove that the elements of $\Sigma_{2n}$ are prime. We proceed by induction on $n \ge 2$. When $n = 2$, we verify directly the result. Now, suppose that the elements of $\Sigma_{2n}$ are prime, where $n \ge 2$. Consider $\sigma \in \Sigma_{2(n+1)}$. Clearly, $\sigma - \{2n, 2n+1\} \in \Sigma_{2n}$. By induction hypothesis, $\sigma - \{2n, 2n+1\}$ is prime. Set

$$ X = \{0, \dots, 2n-1\}. $$

We have $2n+1 \in X_{\sigma}(2n-1)$ and $2n \in \langle X \rangle_{\sigma}$ (see Notation 12). Consider a module $M$ of $\sigma$ such that $|M| \ge 2$. We must show that $M = V(\sigma)$. Since $M \cap X$ is a module of $\sigma[X]$, we have $|M \cap X| \le 1$ or $X \subseteq M$. For a contradiction, suppose that $|M \cap X| \le 1$. Since $2n$ and $2n+1$ do not belong to the same block
module of $\sigma[X \cup \{v, w\}]$, which contradicts the fact that $\sigma[X \cup \{v, w\}]$ is prime. Consequently, we have $\{v, w\} \setminus \langle X \rangle_{\sigma} \neq \emptyset$. It follows from Claim 13 that

$$ \{v, w\} \cap (\mathrm{Ext}_{\sigma}(X) \cup (\bigcup_{y \in X} X_{\sigma}(y))) \neq \emptyset. $$

For instance, assume that $v \in \mathrm{Ext}_{\sigma}(X) \cup (\bigcup_{y \in X} X_{\sigma}(y))$. Clearly, for $t \in X_{\sigma}(y)$, where $y \in X$, we have

$$ \begin{gathered} \mathcal{G}(\sigma[X \cup \{t\}]) = \{\{y,t\}\} \cup \{\{z\} : z \in X \setminus \{y\}\} \\ \text{and} \\ \sigma[X \cup \{t\}]/\mathcal{G}(\sigma[X \cup \{t\}]) \text{ is prime.} \end{gathered} $$

Hence, we can choose $y_0 = v$ and $y_1 = w$. $\square$

**Lemma 17.** Given a 2-structure $\sigma$ such that $v(\sigma) \ge 5$, if $\sigma/\mathcal{G}(\sigma)$ is prime, then there exists $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime as well.

*Proof.* The result is obvious when $\sigma$ is decomposable. Hence, suppose that $\sigma$ is prime. By Corollary 15, there exists $X \neq V(\sigma)$ such that $\sigma[X]$ is prime and $|V(\sigma) \setminus X| \le 2$. To conclude, it suffices to apply Lemma 16. $\square$

## 2.2 Critical 2-structures

A prime 2-structure $\sigma$ is critical if for every $v \in V(\sigma)$, $\sigma - v$ is decomposable. Critical digraphs were characterized by Schmerl and Trotter [14] (see also Boud-abbous and Ille [1]).

**Notation 18.** Given $n \ge 2$, we denote by $\Sigma_{2n}$ the sets of the 2-structures $\sigma$ defined on $V(\sigma) = \{0, \dots, 2n-1\}$ such that $|\tilde{L}_2(\sigma)| = 2$, $\tilde{\sigma}(\{0,1\}) \neq \tilde{\sigma}(\{0,2\})$, and for $p, q \in \{0, \dots, 2n-1\}$ such that $p < q$, we have

$$ \sigma(p, q) = \begin{cases} \sigma(0, 1) & \text{if } p \text{ is even and } q \text{ is odd,} \\ \sigma(0, 2) & \text{otherwise.} \end{cases} \qquad (2) $$

**Claim 19.** Given $n \ge 2$, the elements of $\Sigma_{2n}$ are critical 2-structures.

*Proof.* To begin, we prove that the elements of $\Sigma_{2n}$ are prime. We proceed by induction on $n \ge 2$. When $n = 2$, we verify directly the result. Now, suppose that the elements of $\Sigma_{2n}$ are prime, where $n \ge 2$. Consider $\sigma \in \Sigma_{2(n+1)}$. Clearly, $\sigma - \{2n, 2n+1\} \in \Sigma_{2n}$. By induction hypothesis, $\sigma - \{2n, 2n+1\}$ is prime. Set

$$ X = \{0, \dots, 2n-1\}. $$

We have $2n+1 \in X_{\sigma}(2n-1)$ and $2n \in \langle X \rangle_{\sigma}$ (see Notation 12). Consider a module $M$ of $\sigma$ such that $|M| \ge 2$. We must show that $M = V(\sigma)$. Since $M \cap X$ is a module of $\sigma[X]$, we have $|M \cap X| \le 1$ or $X \subseteq M$. For a contradiction, suppose that $|M \cap X| \le 1$. Since $2n$ and $2n+1$ do not belong to the same block
of $p_{(\sigma,X)}$, $M \neq \{2n, 2n+1\}$. Thus, there exists $y \in X$ such that $M \cap X = \{y\}$. Since $|M| \ge 2$, $M \setminus X \neq \emptyset$. Clearly, $(M \setminus X) \subseteq X_\sigma(y)$. By Claim 13, $p_{(\sigma,X)}$ is a partition of $V(\sigma) \setminus X$. It follows that $M = \{2n-1, 2n+1\}$, which is impossible because $\tilde{\sigma}(\{2n-1, 2n\}) \neq \tilde{\sigma}(\{2n, 2n+1\})$. Consequently, $X \subseteq M$. Clearly, $(V(\sigma) \setminus M) \subseteq \{X\}_\sigma$. Since $p_{(\sigma,X)}$ is a partition of $V(\sigma) \setminus X$, we obtain $2n+1 \in M$. Furthermore, since $\tilde{\sigma}(\{2n-1, 2n\}) \neq \tilde{\sigma}(\{2n, 2n+1\})$, $X \cup \{2n+1\}$ is not a module of $\sigma$. It follows that $M = V(\sigma)$.

Lastly, we verify that elements of $\Sigma_{2n}$ are critical. Given $n \ge 2$, consider $\sigma \in \Sigma_{2n}$. We have

* $\{2, \dots, 2n-1\}$ is a module of $\sigma - 0$;

* $\{0, \dots, 2n-3\}$ is a module of $\sigma - (2n-1)$;

* for each $p \in \{1, \dots, 2n-2\}$, $\{p-1, p+1\}$ is a module of $\sigma - p$.

Therefore, $\sigma$ is critical. $\square$

**Example 20.** Let $n \ge 2$. We consider the graph $G_{2n}$ defined on $V(G_{2n}) = \{0, \dots, 2n-1\}$ by

$$E(G_{2n}) = \{2i(2j+1) : i \le j \in \{0, \dots, n-1\}\}.$$

The graph $G_{2n}$ is critical. Furthermore, $G_{2n}$ is a comparability graph. We consider the unique transitive orientation $Q_{2n}$ of $G_{2n}$ such that $0 <_{Q_{2n}} 1$. The complement of $G_{2n}$ is a comparability graph too. We consider also the unique transitive orientation $R_{2n}$ of the complement of $G_{2n}$ such that $0 <_{R_{2n}} 2$. The partial orders $Q_{2n}$ and $R_{2n}$ are critical. We consider the 2-structure $\gamma_{2n}$ defined on $V(\gamma_{2n}) = \{0, \dots, 2n-1\}$ with $L(\gamma_{2n}) = \mathbb{Z}_5 \setminus \{0\}$ as follows. For distinct $v, w \in V(\gamma_{2n})$,

$$\gamma_{2n}(v, w) = \begin{cases} 1 & \text{if } v <_{Q_{2n}} w, \\ 4 & \text{if } w <_{Q_{2n}} v, \\ 2 & \text{if } v <_{R_{2n}} w, \\ 3 & \text{if } w <_{R_{2n}} v. \end{cases}$$

Clearly, $\gamma_{2n}$ satisfies (2). Furthermore, $\tilde{\gamma}_{2n}(\{0,1\}) = \{1,4\}$ and $\tilde{\gamma}_{2n}(\{0,2\}) = \{2,3\}$. Hence, we have $\tilde{\gamma}_{2n}(\{0,1\}) \neq \tilde{\gamma}_{2n}(\{0,2\})$ and $|\tilde{L}_2(\gamma_{2n})| = 2$. Therefore, $\gamma_{2n} \in \Sigma_{2n}$. It follows from Claim 19 that $\gamma_{2n}$ is critical.

Lastly, suppose for a contradiction that there exists $X \neq V(\gamma_{2n})$ such that $|X|$ is odd and $\gamma_{2n}[X]$ is prime. Since $V(\gamma_{2n})$ is even, it follows from Proposition 14 applied several times that there exists $v \in V(\gamma_{2n})$ such that $\gamma_{2n} - v$ is prime, which contradicts the fact that $\gamma_{2n}$ is critical. Consequently, for every $X \neq V(\gamma_{2n})$ such that $\gamma_{2n}[X]$ is prime, we have $|X|$ is even. Thus, for every $X \neq V(\gamma_{2n})$ such that $|X| = 3$, $\gamma_{2n}[X]$ is decomposable. It follows that $E(G_{\gamma_{2n}}) = \emptyset$, and hence $G_{\gamma_{2n}}$ is disconnected. Therefore, $\gamma_{2n}$ does not satisfy Statement (T1) of Theorem 8.
of $p_{(\sigma,X)}$, $M \neq \{2n, 2n+1\}$. Thus, there exists $y \in X$ such that $M \cap X = \{y\}$. Since $|M| \ge 2$, $M \setminus X \neq \emptyset$. Clearly, $(M \setminus X) \subseteq X_{\sigma}(y)$. By Claim 13, $p_{(\sigma,X)}$ is a partition of $V(\sigma) \setminus X$. It follows that $M = \{2n-1, 2n+1\}$, which is impossible because $\tilde{\sigma}(\{2n-1, 2n\}) \neq \tilde{\sigma}(\{2n, 2n+1\})$. Consequently, $X \subseteq M$. Clearly, $(V(\sigma) \setminus M) \subseteq \{X\}_{\sigma}$. Since $p_{(\sigma,X)}$ is a partition of $V(\sigma) \setminus X$, we obtain $2n+1 \in M$. Furthermore, since $\tilde{\sigma}(\{2n-1, 2n\}) \neq \tilde{\sigma}(\{2n, 2n+1\})$, $X \cup \{2n+1\}$ is not a module of $\sigma$. It follows that $M = V(\sigma)$.

Lastly, we verify that elements of $\Sigma_{2n}$ are critical. Given $n \ge 2$, consider $\sigma \in \Sigma_{2n}$. We have

* $\{2, \dots, 2n-1\}$ is a module of $\sigma - 0$;

* $\{0, \dots, 2n-3\}$ is a module of $\sigma - (2n-1)$;

* for each $p \in \{1, \dots, 2n-2\}$, $\{p-1, p+1\}$ is a module of $\sigma - p$.

Therefore, $\sigma$ is critical. $\square$

**Example 20.** Let $n \ge 2$. We consider the graph $G_{2n}$ defined on $V(G_{2n}) = \{0, \dots, 2n-1\}$ by

$$E(G_{2n}) = \{2i(2j+1) : i \le j \in \{0, \dots, n-1\}\}.$$

The graph $G_{2n}$ is critical. Furthermore, $G_{2n}$ is a comparability graph. We consider the unique transitive orientation $Q_{2n}$ of $G_{2n}$ such that $0 <_{Q_{2n}} 1$. The complement of $G_{2n}$ is a comparability graph too. We consider also the unique transitive orientation $R_{2n}$ of the complement of $G_{2n}$ such that $0 <_{R_{2n}} 2$. The partial orders $Q_{2n}$ and $R_{2n}$ are critical. We consider the 2-structure $\gamma_{2n}$ defined on $V(\gamma_{2n}) = \{0, \dots, 2n-1\}$ with $L(\gamma_{2n}) = \mathbb{Z}_5 \setminus \{0\}$ as follows. For distinct $v, w \in V(\gamma_{2n})$,

$$\gamma_{2n}(v, w) = \begin{cases} 1 & \text{if } v <_{Q_{2n}} w, \\ 4 & \text{if } w <_{Q_{2n}} v, \\ 2 & \text{if } v <_{R_{2n}} w, \\ 3 & \text{if } w <_{R_{2n}} v. \end{cases}$$

Clearly, $\gamma_{2n}$ satisfies (2). Furthermore, $\tilde{\gamma}_{2n}(\{0,1\}) = \{1,4\}$ and $\tilde{\gamma}_{2n}(\{0,2\}) = \{2,3\}$. Hence, we have $\tilde{\gamma}_{2n}(\{0,1\}) \neq \tilde{\gamma}_{2n}(\{0,2\})$ and $|\tilde{L}_2(\gamma_{2n})| = 2$. Therefore, $\gamma_{2n} \in \Sigma_{2n}$. It follows from Claim 19 that $\gamma_{2n}$ is critical.

Lastly, suppose for a contradiction that there exists $X \neq V(\gamma_{2n})$ such that $|X|$ is odd and $\gamma_{2n}[X]$ is prime. Since $V(\gamma_{2n})$ is even, it follows from Proposition 14 applied several times that there exists $v \in V(\gamma_{2n})$ such that $\gamma_{2n} - v$ is prime, which contradicts the fact that $\gamma_{2n}$ is critical. Consequently, for every $X \neq V(\gamma_{2n})$ such that $\gamma_{2n}[X]$ is prime, we have $|X|$ is even. Thus, for every $X \neq V(\gamma_{2n})$ such that $|X| = 3$, $\gamma_{2n}[X]$ is decomposable. It follows that $E(G_{\gamma_{2n}}) = \emptyset$, and hence $G_{\gamma_{2n}}$ is disconnected. Therefore, $\gamma_{2n}$ does not satisfy Statement (T1) of Theorem 8.
### 3 The 3-hemimorphy

The next result is obvious.

**Fact 21.** A 2-structure $\sigma$ is 2-forced if and only if $|E_2(\sigma)| \le 1$.

Consider 2-hemimorphic 2-structures $\sigma$ and $\tau$. We associate to $\sigma$ and $\tau$ the graph $\mathcal{E}(\sigma, \tau)$ defined on $V(\sigma)$ as follows. For distinct $v, w \in V(\sigma)$, $vw \in E(\mathcal{E}(\sigma, \tau))$ if $\sigma(v, w) = \tau(v, w)$ and $\{v, w\} \in E_2(\sigma)$. We associate also to $\sigma$ and $\tau$ the graph $\mathcal{D}(\sigma, \tau)$ defined on $V(\sigma)$ as follows. For distinct $v, w \in V(\sigma)$, $vw \in E(\mathcal{D}(\sigma, \tau))$ if $\sigma(v, w) \neq \tau(v, w)$ (and hence $\{v, w\} \in E_2(\sigma)$). Note that

$$ \left\{ \begin{array}{l} \mathcal{D}(\sigma, \tau) = \mathcal{E}(\sigma, \tau^*), \\ \text{and} \\ E(\mathcal{D}(\sigma, \tau)) \cup E(\mathcal{E}(\sigma, \tau)) = E_2(\sigma). \end{array} \right. \qquad (3) $$

Thus,

$$ \text{if } E_1(\sigma) = \emptyset, \text{ then } \mathcal{E}(\sigma, \tau) \text{ is the complement of } \mathcal{D}(\sigma, \tau). \qquad (4) $$

**Definition 22.** Let $\sigma$ be a 2-structure. Given $W \subseteq V(\sigma)$, the 2-structure $\text{Inv}(\sigma, W)$ is defined on $V(\text{Inv}(\sigma, W)) = V(\sigma)$ as follows. Given distinct $v, w \in V(\text{Inv}(\sigma, W))$,

$$ \text{Inv}(\sigma, W)(v, w) = \begin{cases} \sigma(w, v) & \text{if } v, w \in W \\ \sigma(v, w) & \text{otherwise.} \end{cases} $$

It is easy to show the next fact.

**Fact 23.** Let $\sigma$ be a 2-structure. For a module $M$ of $\sigma$, $\sigma$ and $\text{Inv}(\sigma, M)$ are 3-hemimorphic.

**Fact 24.** Given 3-hemimorphic 2-structures $\sigma$ and $\tau$ such that $v(\sigma) = 3$. If $E(\mathcal{D}(\sigma, \tau))$ and $E(\mathcal{E}(\sigma, \tau))$ are nonempty, then there exist distinct $v, w \in V(\sigma)$ such that

* $\{v, w\}$ is a module of $\sigma$ and $\tau$;

* $E(\mathcal{D}(\sigma, \tau)) = \{vw\}$ or $E(\mathcal{E}(\sigma, \tau)) = \{vw\}$;

* $E_1(\sigma) = \emptyset$ (so $\mathcal{E}(\sigma, \tau)$ is the complement of $\mathcal{D}(\sigma, \tau)$ by (4)).

*Proof.* We can assume that $V(\sigma) = \{0, 1, 2\}$, $01 \in E(\mathcal{D}(\sigma, \tau))$, and $02 \in E(\mathcal{E}(\sigma, \tau))$. If $|\tilde{L}(\sigma)| = 3$, then the only isomorphism from $\sigma$ onto $\tau$ or $\tau^*$ is $\text{Id}_{\{0,1,2\}}$, which is impossible because $E(\mathcal{D}(\sigma, \tau))$ and $E(\mathcal{E}(\sigma, \tau))$ are nonempty. It follows that $|\tilde{L}(\sigma)| \le 2$.

To begin, suppose that $\tilde{\sigma}(\{0, 1\}) = \tilde{\sigma}(\{0, 2\})$. If $\tilde{\sigma}(\{0, 1\}) \neq \tilde{\sigma}(\{1, 2\})$, then one among $\sigma$ or $\tau$ is prime whereas the other one is decomposable. It follows that $\tilde{\sigma}(\{0, 1\}) = \tilde{\sigma}(\{1, 2\})$. Hence, $\sigma$ and $\tau$ are linear. Moreover, we obtain that $\{1, 2\}$ is a module of $\sigma$ or $\tau$. For instance, assume that $\{1, 2\}$ is a module of $\sigma$.
### 3 The 3-hemimorphy

The next result is obvious.

**Fact 21.** A 2-structure $\sigma$ is 2-forced if and only if $|E_2(\sigma)| \le 1$.

Consider 2-hemimorphic 2-structures $\sigma$ and $\tau$. We associate to $\sigma$ and $\tau$ the graph $\mathcal{E}(\sigma, \tau)$ defined on $V(\sigma)$ as follows. For distinct $v, w \in V(\sigma)$, $vw \in E(\mathcal{E}(\sigma, \tau))$ if $\sigma(v, w) = \tau(v, w)$ and $\{v, w\} \in E_2(\sigma)$. We associate also to $\sigma$ and $\tau$ the graph $\mathcal{D}(\sigma, \tau)$ defined on $V(\sigma)$ as follows. For distinct $v, w \in V(\sigma)$, $vw \in E(\mathcal{D}(\sigma, \tau))$ if $\sigma(v, w) \neq \tau(v, w)$ (and hence $\{v, w\} \in E_2(\sigma)$). Note that

$$ \left\{ \begin{array}{l} \mathcal{D}(\sigma, \tau) = \mathcal{E}(\sigma, \tau^*), \\ \text{and} \\ E(\mathcal{D}(\sigma, \tau)) \cup E(\mathcal{E}(\sigma, \tau)) = E_2(\sigma). \end{array} \right. \qquad (3) $$

Thus,

$$ \text{if } E_1(\sigma) = \emptyset, \text{ then } \mathcal{E}(\sigma, \tau) \text{ is the complement of } \mathcal{D}(\sigma, \tau). \qquad (4) $$

**Definition 22.** Let $\sigma$ be a 2-structure. Given $W \subseteq V(\sigma)$, the 2-structure $\text{Inv}(\sigma, W)$ is defined on $V(\text{Inv}(\sigma, W)) = V(\sigma)$ as follows. Given distinct $v, w \in V(\text{Inv}(\sigma, W))$,

$$ \text{Inv}(\sigma, W)(v, w) = \begin{cases} \sigma(w, v) & \text{if } v, w \in W \\ \sigma(v, w) & \text{otherwise.} \end{cases} $$

It is easy to show the next fact.

**Fact 23.** Let $\sigma$ be a 2-structure. For a module $M$ of $\sigma$, $\sigma$ and $\text{Inv}(\sigma, M)$ are 3-hemimorphic.

**Fact 24.** Given 3-hemimorphic 2-structures $\sigma$ and $\tau$ such that $v(\sigma) = 3$. If $E(\mathcal{D}(\sigma, \tau))$ and $E(\mathcal{E}(\sigma, \tau))$ are nonempty, then there exist distinct $v, w \in V(\sigma)$ such that

* $\{v, w\}$ is a module of $\sigma$ and $\tau$;

* $E(\mathcal{D}(\sigma, \tau)) = \{vw\}$ or $E(\mathcal{E}(\sigma, \tau)) = \{vw\}$;

* $E_1(\sigma) = \emptyset$ (so $\mathcal{E}(\sigma, \tau)$ is the complement of $\mathcal{D}(\sigma, \tau)$ by (4)).

*Proof.* We can assume that $V(\sigma) = \{0, 1, 2\}$, $01 \in E(\mathcal{D}(\sigma, \tau))$, and $02 \in E(\mathcal{E}(\sigma, \tau))$. If $|\tilde{L}(\sigma)| = 3$, then the only isomorphism from $\sigma$ onto $\tau$ or $\tau^*$ is $\text{Id}_{\{0,1,2\}}$, which is impossible because $E(\mathcal{D}(\sigma, \tau))$ and $E(\mathcal{E}(\sigma, \tau))$ are nonempty. It follows that $|\tilde{L}(\sigma)| \le 2$.

To begin, suppose that $\tilde{\sigma}(\{0, 1\}) = \tilde{\sigma}(\{0, 2\})$. If $\tilde{\sigma}(\{0, 1\}) \neq \tilde{\sigma}(\{1, 2\})$, then one among $\sigma$ or $\tau$ is prime whereas the other one is decomposable. It follows that $\tilde{\sigma}(\{0, 1\}) = \tilde{\sigma}(\{1, 2\})$. Hence, $\sigma$ and $\tau$ are linear. Moreover, we obtain that $\{1, 2\}$ is a module of $\sigma$ or $\tau$. For instance, assume that $\{1, 2\}$ is a module of $\sigma$.
By exchanging $\tau$ and $\tau^*$ if necessary, we can assume that $12 \in E(\mathcal{D}(\sigma, \tau))$. We obtain that $\{0,2\}$ is a module of $\sigma$ and $\tau$. Furthermore, $E(\mathcal{E}(\sigma, \tau)) = \{02\}$.

Now, suppose that $\tilde{\sigma}(\{0,1\}) \neq \tilde{\sigma}(\{0,2\})$. Since $|\tilde{L}(\sigma)| \leq 2$, we can assume that $\tilde{\sigma}(\{0,1\}) = \tilde{\sigma}(\{1,2\})$. For a contradiction, suppose that $\{0,2\}$ is not a module of $\sigma$. Since $\sigma$ and $\tau$ are both prime or not, we obtain $12 \in E(\mathcal{D}(\sigma, \tau))$. It is not difficult to verify that $\sigma$ is isomorphic neither to $\tau$ nor to $\tau^*$. Consequently, $\{0,2\}$ is a module of $\sigma$. Hence, $\tau$ is decomposable. It follows that $E(\mathcal{E}(\sigma, \tau)) = \{02\}$, and hence $\{0,2\}$ is a module of $\tau$. $\square$

The next fact is an immediate consequence of Fact 24.

**Fact 25.** Given a 2-structure $\sigma$ such that $v(\sigma) = 3$, if $\sigma$ is prime, then $\sigma$ is 3-forced.

It is not difficult to show the next result. Nevertheless, we have to adopt
the following convention.

**Convention 26.** Let $\sigma$ and $\tau$ be 2-hemimorphic 2-structures. We have $\tilde{L}(\sigma) = \tilde{L}(\tau)$, and hence $\tilde{L}_1(\sigma) = \tilde{L}_1(\tau)$. Suppose that $|\tilde{L}_1(\sigma)| \ge 2$. We choose the same $l \in L(\sigma) \cap L(\tau)$ such that $\{l\} \in \tilde{L}_1(\sigma) \cap \tilde{L}_1(\tau)$ to define $\vec{\sigma}$ and $\vec{\tau}$. Otherwise, $\vec{\sigma}$ and $\vec{\tau}$ would not be 2-hemimorphic.

**Lemma 27.** *Given 2-hemimorphic 2-structures $\sigma$ and $\tau$, $\sigma$ and $\tau$ are 3-hemimorphic if and only if $\vec{\sigma}$ and $\vec{\tau}$ are 3-hemimorphic too.*

Now, we are ready to prove Lemma 6 (with Convention 26).

*Proof of Lemma 6.* To begin, suppose that $\sigma$ is 3-forced. Consider a 2-structure $\tau$ which is 3-hemimorphic to $\vec{\sigma}$. There exists a unique 2-structure $\rho$ such that $\sigma$ and $\rho$ are 2-hemimorphic and $\vec{\rho} = \tau$. By Lemma 27, $\sigma$ and $\rho$ are 3-hemimorphic. Since $\sigma$ is 3-forced, we obtain $\sigma = \tau$ or $\tau^*$. It follows that $\vec{\sigma} = \vec{\rho}$ or $(\vec{\rho})^*$.

Conversely, suppose that $\vec{\sigma}$ is 3-forced. Consider a 2-structure $\tau$ which is 3-hemimorphic to $\sigma$. By Lemma 27, $\vec{\sigma}$ and $\vec{\tau}$ are 3-hemimorphic. Since $\vec{\sigma}$ is 3-forced, we obtain $\vec{\sigma} = \vec{\tau}$ or $(\vec{\tau})^*$. Since $\sigma$ and $\tau$ are 2-hemimorphic, we have $\sigma = \tau$ or $\tau^*$. $\square$

**Example 28.** Consider a set $S$ admitting a partition $P = \{X_0, \dots, X_{n-1}\}$, where $n \ge 4$. We consider the partial order $O$ defined on $S$ satisfying

• $P$ is a modular partition of $O$;

• $O/P$ is the linear order $X_0 < X_1 < \dots < X_{n-1}$;

• for each $i \in \{0, \dots, n-1\}$, the arc set of $O[X_i]$ is empty.

Moreover, we consider the partial order $Q$ defined on $S$ satisfying

• $P$ is a modular partition of $Q$;

• $O/P$ is the linear order $X_2 < X_0 < X_3 < \dots \le X_{n-1} < X_1$;
By exchanging $\tau$ and $\tau^*$ if necessary, we can assume that $12 \in E(\mathcal{D}(\sigma, \tau))$. We obtain that $\{0,2\}$ is a module of $\sigma$ and $\tau$. Furthermore, $E(\mathcal{E}(\sigma, \tau)) = \{02\}$.

Now, suppose that $\tilde{\sigma}(\{0,1\}) \neq \tilde{\sigma}(\{0,2\})$. Since $|\tilde{L}(\sigma)| \le 2$, we can assume that $\tilde{\sigma}(\{0,1\}) = \tilde{\sigma}(\{1,2\})$. For a contradiction, suppose that $\{0,2\}$ is not a module of $\sigma$. Since $\sigma$ and $\tau$ are both prime or not, we obtain $12 \in E(\mathcal{D}(\sigma, \tau))$. It is not difficult to verify that $\sigma$ is isomorphic neither to $\tau$ nor to $\tau^*$. Consequently, $\{0,2\}$ is a module of $\sigma$. Hence, $\tau$ is decomposable. It follows that $E(\mathcal{E}(\sigma, \tau)) = \{02\}$, and hence $\{0,2\}$ is a module of $\tau$. $\square$

The next fact is an immediate consequence of Fact 24.

**Fact 25.** Given a 2-structure $\sigma$ such that $v(\sigma) = 3$, if $\sigma$ is prime, then $\sigma$ is 3-forced.

It is not difficult to show the next result. Nevertheless, we have to adopt
the following convention.

**Convention 26.** Let $\sigma$ and $\tau$ be 2-hemimorphic 2-structures. We have $\tilde{L}(\sigma) = \tilde{L}(\tau)$, and hence $\tilde{L}_1(\sigma) = \tilde{L}_1(\tau)$. Suppose that $|\tilde{L}_1(\sigma)| \ge 2$. We choose the same $l \in L(\sigma) \cap L(\tau)$ such that $\{l\} \in \tilde{L}_1(\sigma) \cap \tilde{L}_1(\tau)$ to define $\vec{\sigma}$ and $\vec{\tau}$. Otherwise, $\vec{\sigma}$ and $\vec{\tau}$ would not be 2-hemimorphic.

**Lemma 27.** *Given 2-hemimorphic 2-structures $\sigma$ and $\tau$, $\sigma$ and $\tau$ are 3-hemimorphic if and only if $\vec{\sigma}$ and $\vec{\tau}$ are 3-hemimorphic too.*

Now, we are ready to prove Lemma 6 (with Convention 26).

*Proof of Lemma 6.* To begin, suppose that $\sigma$ is 3-forced. Consider a 2-structure $\tau$ which is 3-hemimorphic to $\vec{\sigma}$. There exists a unique 2-structure $\rho$ such that $\sigma$ and $\rho$ are 2-hemimorphic and $\vec{\rho} = \tau$. By Lemma 27, $\sigma$ and $\rho$ are 3-hemimorphic. Since $\sigma$ is 3-forced, we obtain $\sigma = \tau$ or $\tau^*$. It follows that $\vec{\sigma} = \vec{\rho}$ or $(\vec{\rho})^*$.

Conversely, suppose that $\vec{\sigma}$ is 3-forced. Consider a 2-structure $\tau$ which is 3-hemimorphic to $\sigma$. By Lemma 27, $\vec{\sigma}$ and $\vec{\tau}$ are 3-hemimorphic. Since $\vec{\sigma}$ is 3-forced, we obtain $\vec{\sigma} = \vec{\tau}$ or $(\vec{\tau})^*$. Since $\sigma$ and $\tau$ are 2-hemimorphic, we have $\sigma = \tau$ or $\tau^*$. $\square$

**Example 28.** Consider a set $S$ admitting a partition $P = \{X_0, \dots, X_{n-1}\}$, where $n \ge 4$. We consider the partial order $O$ defined on $S$ satisfying

• $P$ is a modular partition of $O$;

• $O/P$ is the linear order $X_0 < X_1 < \dots < X_{n-1}$;

• for each $i \in \{0, \dots, n-1\}$, the arc set of $O[X_i]$ is empty.

Moreover, we consider the partial order $Q$ defined on $S$ satisfying

• $P$ is a modular partition of $Q$;

• $O/P$ is the linear order $X_2 < X_0 < X_3 < \dots \le X_{n-1} < X_1$;
• for each $i \in \{0, \dots, n-1\}$, the arc set of $Q[X_i]$ is empty.

Clearly, $\sigma_O$ and $\sigma_Q$ are 3-hemimorphic. It is not difficult to verify that $P$ is also a modular partition of $\mathcal{D}(\sigma_O, \sigma_Q)$ and $\mathcal{E}(\sigma_O, \sigma_Q)$ such that

• $E(\mathcal{D}(\sigma_O, \sigma_Q)/P) = \{X_0X_2\} \cup \{X_1X_i : i \in \{2, \dots, n-1\}\}$;

• $\mathcal{E}(\sigma_O, \sigma_Q)/P$ is the complement of $\mathcal{D}(\sigma_O, \sigma_Q)/P$.

It follows that $\mathcal{D}(\sigma_O, \sigma_Q)$ and $\mathcal{E}(\sigma_O, \sigma_Q)$ are both connected. Hence, $\sigma_O$ is not 3-forced. It is not difficult to verify that $P = \mathcal{G}(\sigma_O)$ and $\sigma_O/\mathcal{G}(\sigma_O)$ is linear; whence the necessity of Statement (T3) in Theorem 8. Furthermore, $X_0 \cup X_1$ is a module of $\sigma_O$ such that $E_2(\sigma[X_0 \cup X_1]) \neq \emptyset$; whence the necessity of Statement (T4) in Theorem 42.

**Example 29.** Given $n \ge 2$, consider the critical 2-structures $\gamma_{2n}$ introduced in Example 20. We consider also the 2-structure $\rho_{2n}$ defined on $V(\rho_{2n}) = \{0, \dots, 2n-1\}$ in the following manner. For any $p, q \in \{0, \dots, 2n-1\}$ such that $p < q$,

$$ \rho_{2n}(p, q) = \begin{cases} \gamma_{2n}(q, p) & \text{if } p \text{ is even and } q \text{ is odd,} \\ \gamma_{2n}(p, q) & \text{otherwise.} \end{cases} \qquad (5) $$

By Claim 19, $\rho_{2n}$ is critical. It is not difficult to verify that $\gamma_{2n}$ and $\rho_{2n}$ are 3-hemimorphic. Nevertheless, by considering $\{0, 1, 2, 3\}$, we see that $\gamma_{2n}$ and $\rho_{2n}$ are not 4-hemimorphic. Clearly, we have

$$ E(\mathcal{D}(\gamma_{2n}, \rho_{2n})) = E(G_{2n}) \text{ (see Example 20).} $$

By (3), $\mathcal{E}(\gamma_{2n}, \rho_{2n})$ is the complement of $\mathcal{D}(\gamma_{2n}, \rho_{2n})$. It follows that $\mathcal{D}(\gamma_{2n}, \rho_{2n})$ and $\mathcal{E}(\gamma_{2n}, \rho_{2n})$ are both connected. Hence, $\gamma_{2n}$ is not 3-forced (see Problem 41). As seen in Example 20, $\gamma_{2n}$ does not satisfy Statement (T1) of Theorem 8; whence the necessity of Statement (T1) in Theorem 8.

**Fact 30.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $v(\sigma) = 4$. If $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected, and if $\sigma/\mathcal{G}(\sigma)$ is prime, then there exists an isomorphism $\varphi$ from $\sigma$ onto an element of $\Sigma_4$ (see Notation 18), which is also an isomorphism from $\mathcal{D}(\sigma, \tau)$ onto $G_4$ (see Example 20).

*Proof.* Since $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are connected, $K_{1,3}$ and $K_3$ do not embed into $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$. It follows that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are isomorphic to $P_4$. Hence, $\mathcal{D}(\sigma, \tau)$ is the complement of $\mathcal{E}(\sigma, \tau)$. Up to isomorphism, we can assume that $V(\sigma) = \{0, 1, 2, 3\}$ and $\mathcal{D}(\sigma, \tau) = G_4$. Since $01, 03 \in E(\mathcal{D}(\sigma, \tau))$ and $13 \in E(\mathcal{E}(\sigma, \tau))$, it follows from Fact 24 that $\{1, 3\}$ is a module of $\sigma[\{0, 1, 3\}]$. Hence, we have $\sigma(0, 1) = \sigma(0, 3)$. Similarly, we have $\sigma(0, 3) = \sigma(2, 3)$ and $\sigma(0, 2) = \sigma(1, 2) = \sigma(1, 3)$. Therefore, $\sigma$ satisfies (2). If $\tilde{\sigma}(\{0, 1\}) = \tilde{\sigma}(\{0, 2\})$, then $\sigma$ is linear, which contradicts the fact that $\sigma/\mathcal{G}(\sigma)$ is prime. It follows that $\tilde{\sigma}(\{0, 1\}) \neq \tilde{\sigma}(\{0, 2\})$. Thus, $\sigma \in \Sigma_4$. $\square$
• for each $i \in \{0, \dots, n-1\}$, the arc set of $Q[X_i]$ is empty.

Clearly, $\sigma_O$ and $\sigma_Q$ are 3-hemimorphic. It is not difficult to verify that $P$ is also a modular partition of $\mathcal{D}(\sigma_O, \sigma_Q)$ and $\mathcal{E}(\sigma_O, \sigma_Q)$ such that

• $E(\mathcal{D}(\sigma_O, \sigma_Q)/P) = \{X_0X_2\} \cup \{X_1X_i : i \in \{2, \dots, n-1\}\}$;

• $\mathcal{E}(\sigma_O, \sigma_Q)/P$ is the complement of $\mathcal{D}(\sigma_O, \sigma_Q)/P$.

It follows that $\mathcal{D}(\sigma_O, \sigma_Q)$ and $\mathcal{E}(\sigma_O, \sigma_Q)$ are both connected. Hence, $\sigma_O$ is not 3-forced. It is not difficult to verify that $P = \mathcal{G}(\sigma_O)$ and $\sigma_O/\mathcal{G}(\sigma_O)$ is linear; whence the necessity of Statement (T3) in Theorem 8. Furthermore, $X_0 \cup X_1$ is a module of $\sigma_O$ such that $E_2(\sigma[X_0 \cup X_1]) \neq \emptyset$; whence the necessity of Statement (T4) in Theorem 42.

**Example 29.** Given $n \ge 2$, consider the critical 2-structures $\gamma_{2n}$ introduced in Example 20. We consider also the 2-structure $\rho_{2n}$ defined on $V(\rho_{2n}) = \{0, \dots, 2n-1\}$ in the following manner. For any $p, q \in \{0, \dots, 2n-1\}$ such that $p < q$,

$$ \rho_{2n}(p, q) = \begin{cases} \gamma_{2n}(q, p) & \text{if } p \text{ is even and } q \text{ is odd,} \\ \gamma_{2n}(p, q) & \text{otherwise.} \end{cases} \qquad (5) $$

By Claim 19, $\rho_{2n}$ is critical. It is not difficult to verify that $\gamma_{2n}$ and $\rho_{2n}$ are 3-hemimorphic. Nevertheless, by considering $\{0, 1, 2, 3\}$, we see that $\gamma_{2n}$ and $\rho_{2n}$ are not 4-hemimorphic. Clearly, we have

$$ E(\mathcal{D}(\gamma_{2n}, \rho_{2n})) = E(G_{2n}) \text{ (see Example 20).} $$

By (3), $\mathcal{E}(\gamma_{2n}, \rho_{2n})$ is the complement of $\mathcal{D}(\gamma_{2n}, \rho_{2n})$. It follows that $\mathcal{D}(\gamma_{2n}, \rho_{2n})$ and $\mathcal{E}(\gamma_{2n}, \rho_{2n})$ are both connected. Hence, $\gamma_{2n}$ is not 3-forced (see Problem 41). As seen in Example 20, $\gamma_{2n}$ does not satisfy Statement (T1) of Theorem 8; whence the necessity of Statement (T1) in Theorem 8.

**Fact 30.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $v(\sigma) = 4$. If $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected, and if $\sigma/\mathcal{G}(\sigma)$ is prime, then there exists an isomorphism $\varphi$ from $\sigma$ onto an element of $\Sigma_4$ (see Notation 18), which is also an isomorphism from $\mathcal{D}(\sigma, \tau)$ onto $G_4$ (see Example 20).

*Proof.* Since $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are connected, $K_{1,3}$ and $K_3$ do not embed into $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$. It follows that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are isomorphic to $P_4$. Hence, $\mathcal{D}(\sigma, \tau)$ is the complement of $\mathcal{E}(\sigma, \tau)$. Up to isomorphism, we can assume that $V(\sigma) = \{0, 1, 2, 3\}$ and $\mathcal{D}(\sigma, \tau) = G_4$. Since $01, 03 \in E(\mathcal{D}(\sigma, \tau))$ and $13 \in E(\mathcal{E}(\sigma, \tau))$, it follows from Fact 24 that $\{1, 3\}$ is a module of $\sigma[\{0, 1, 3\}]$. Hence, we have $\sigma(0, 1) = \sigma(0, 3)$. Similarly, we have $\sigma(0, 3) = \sigma(2, 3)$ and $\sigma(0, 2) = \sigma(1, 2) = \sigma(1, 3)$. Therefore, $\sigma$ satisfies (2). If $\tilde{\sigma}(\{0, 1\}) = \tilde{\sigma}(\{0, 2\})$, then $\sigma$ is linear, which contradicts the fact that $\sigma/\mathcal{G}(\sigma)$ is prime. It follows that $\tilde{\sigma}(\{0, 1\}) \neq \tilde{\sigma}(\{0, 2\})$. Thus, $\sigma \in \Sigma_4$. $\square$
**Definition 31.** Recall that a digraph is a flag [9] if it is isomorphic to the digraph ({0, 1, 2}, {01, 10, 12}). A simple generalization to 2-structures follows. A 2-structure $\sigma$ defined on $V(\sigma) = \{0, 1, 2\}$ is a flag if $|\tilde{L}_1(\sigma)| = 2$ and $|\tilde{L}_2(\sigma)| = 1$.

Hagendorf and Lopez [9] showed the next result for digraphs. The generalization to 2-structures is not difficult. Its proof uses mainly Fact 24.

**Fact 32.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $\sigma$ does not contain flags. Each component of $D(\sigma, \tau)$ (or of $\mathcal{E}(\sigma, \tau)$) is a module of $\sigma$ and $\tau$.

**Lemma 33.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $v(\sigma) \ge 5$. If $D(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected and if $\sigma/\mathcal{G}(\sigma)$ is prime, then the following two statements hold

1. there exists $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime;

2. for each $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime, $D(\sigma - v, \tau - v)$ and $\mathcal{E}(\sigma - v, \tau - v)$ are both connected.

*Proof.* We begin with the following observation. Consider 3-hemimorphic 2-structures $\gamma$ and $\rho$. By Lemma 27, $\vec{\gamma}$ and $\vec{\tau}$ are 3-hemimorphic. We have $D(\gamma, \rho) = D(\vec{\gamma}, \vec{\rho})$ and $\mathcal{E}(\gamma, \rho) = \mathcal{E}(\vec{\gamma}, \vec{\rho})$. Moreover, suppose that the graph $(V(\gamma), E_2(\gamma))$ is connected. It follows from Theorem 4 that $\gamma/\mathcal{G}(\gamma)$ is linear or prime. Similarly, it follows from Theorem 4 that $\vec{\gamma}/\mathcal{G}(\vec{\gamma})$ is linear or prime. Clearly, $\gamma/\mathcal{G}(\gamma)$ is linear if and only if $\vec{\gamma}/\mathcal{G}(\vec{\gamma})$ is as well. Therefore, $\gamma/\mathcal{G}(\gamma)$ is prime if and only if $\vec{\gamma}/\mathcal{G}(\vec{\gamma})$ is as well.

Consequently, we can assume that $\sigma = \vec{\sigma}$ and $\tau = \vec{\tau}$. In particular, $\sigma$ and $\tau$ do not contain flags.

The first statement follows from Lemma 17. For the second statement, consider $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime. For a contradiction, suppose that $D(\sigma - v, \tau - v)$ and $\mathcal{E}(\sigma - v, \tau - v)$ are not both connected. By exchanging $\sigma - v$ and $(\sigma - v)^*$ if necessary, we can assume that $D(\sigma - v, \tau - v)$ is disconnected. By Fact 32, the components of $D(\sigma - v, \tau - v)$ are modules of $\sigma - v$ and $\tau - v$. Since $\mathcal{E}(\sigma, \tau)$ is connected, there exists $x \in V(\sigma) \setminus \{v\}$ such that

$$xv \in E(\mathcal{E}(\sigma, \tau)).$$

Denote by $C$ the component of $D(\sigma - v, \tau - v)$ containing $x$. Furthermore, since $(\sigma - v)/\mathcal{G}(\sigma - v)$ is not linear, there exists a component $D$ of $D(\sigma - v, \tau - v)$ such that $D \neq C$ and $\sigma(z, x) \neq \sigma(v, x)$ for $z \in D$. Lastly, recall that $D(\sigma, \tau)$ is connected. By considering a shortest path in $D(\sigma, \tau)$ from $v$ to an element of $D$, we obtain $z \in D$ such that

$$zv \in E(D(\sigma, \tau)).$$

It follows from Fact 24 that $\sigma[\{x, z, v\}]$ and $\tau[\{x, z, v\}]$ are not 3-hemimorphic, which contradicts the fact that $\sigma$ and $\tau$ are 3-hemimorphic. Consequently, $D(\sigma - v, \tau - v)$ and $\mathcal{E}(\sigma - v, \tau - v)$ are both connected. $\square$
**Definition 31.** Recall that a digraph is a flag [9] if it is isomorphic to the digraph ({0, 1, 2}, {01, 10, 12}). A simple generalization to 2-structures follows. A 2-structure $\sigma$ defined on $V(\sigma) = \{0, 1, 2\}$ is a flag if $|\tilde{L}_1(\sigma)| = 2$ and $|\tilde{L}_2(\sigma)| = 1$.

Hagendorf and Lopez [9] showed the next result for digraphs. The generalization to 2-structures is not difficult. Its proof uses mainly Fact 24.

**Fact 32.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $\sigma$ does not contain flags. Each component of $\mathcal{D}(\sigma, \tau)$ (or of $\mathcal{E}(\sigma, \tau)$) is a module of $\sigma$ and $\tau$.

**Lemma 33.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $v(\sigma) \ge 5$. If $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected and if $\sigma/\mathcal{G}(\sigma)$ is prime, then the following two statements hold

1. there exists $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime;

2. for each $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime, $\mathcal{D}(\sigma - v, \tau - v)$ and $\mathcal{E}(\sigma - v, \tau - v)$ are both connected.

*Proof.* We begin with the following observation. Consider 3-hemimorphic 2-structures $\gamma$ and $\rho$. By Lemma 27, $\vec{\gamma}$ and $\vec{\tau}$ are 3-hemimorphic. We have $\mathcal{D}(\gamma, \rho) = \mathcal{D}(\vec{\gamma}, \vec{\rho})$ and $\mathcal{E}(\gamma, \rho) = \mathcal{E}(\vec{\gamma}, \vec{\rho})$. Moreover, suppose that the graph $(V(\gamma), E_2(\gamma))$ is connected. It follows from Theorem 4 that $\gamma/\mathcal{G}(\gamma)$ is linear or prime. Similarly, it follows from Theorem 4 that $\vec{\gamma}/\mathcal{G}(\vec{\gamma})$ is linear or prime. Clearly, $\gamma/\mathcal{G}(\gamma)$ is linear if and only if $\vec{\gamma}/\mathcal{G}(\vec{\gamma})$ is as well. Therefore, $\gamma/\mathcal{G}(\gamma)$ is prime if and only if $\vec{\gamma}/\mathcal{G}(\vec{\gamma})$ is as well.

Consequently, we can assume that $\sigma = \vec{\sigma}$ and $\tau = \vec{\tau}$. In particular, $\sigma$ and $\tau$ do not contain flags.

The first statement follows from Lemma 17. For the second statement, consider $v \in V(\sigma)$ such that $(\sigma - v)/\mathcal{G}(\sigma - v)$ is prime. For a contradiction, suppose that $\mathcal{D}(\sigma - v, \tau - v)$ and $\mathcal{E}(\sigma - v, \tau - v)$ are not both connected. By exchanging $\sigma - v$ and $(\sigma - v)^*$ if necessary, we can assume that $\mathcal{D}(\sigma - v, \tau - v)$ is disconnected. By Fact 32, the components of $\mathcal{D}(\sigma - v, \tau - v)$ are modules of $\sigma - v$ and $\tau - v$. Since $\mathcal{E}(\sigma, \tau)$ is connected, there exists $x \in V(\sigma) \setminus \{v\}$ such that

$$xv \in E(\mathcal{E}(\sigma, \tau)).$$

Denote by $C$ the component of $\mathcal{D}(\sigma - v, \tau - v)$ containing $x$. Furthermore, since $(\sigma - v)/\mathcal{G}(\sigma - v)$ is not linear, there exists a component $D$ of $\mathcal{D}(\sigma - v, \tau - v)$ such that $D \neq C$ and $\sigma(z, x) \neq \sigma(v, x)$ for $z \in D$. Lastly, recall that $\mathcal{D}(\sigma, \tau)$ is connected. By considering a shortest path in $\mathcal{D}(\sigma, \tau)$ from $v$ to an element of $D$, we obtain $z \in D$ such that

$$zv \in E(\mathcal{D}(\sigma, \tau)).$$

It follows from Fact 24 that $\sigma[\{x, z, v\}]$ and $\tau[\{x, z, v\}]$ are not 3-hemimorphic, which contradicts the fact that $\sigma$ and $\tau$ are 3-hemimorphic. Consequently, $\mathcal{D}(\sigma - v, \tau - v)$ and $\mathcal{E}(\sigma - v, \tau - v)$ are both connected. $\square$
The next result is an immediate consequence of Fact 30 and Lemma 33.

**Corollary 34.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $v(\sigma) \ge 4$. If $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected and if $\sigma/\mathcal{G}(\sigma)$ is prime, then there exists $W \subseteq V(\sigma)$ such that $\sigma[W]$ and $\tau[W]$ are isomorphic to an element of $\Sigma_4$ (see Notation 18).

**Remark 35.** Consider 3-hemimorphic digraphs $D$ and $\Delta$. The definitions of the modular partition $\mathcal{G}(D)$ and of the graphs $\mathcal{D}(D, \Delta)$ and $\mathcal{E}(D, \Delta)$ in [5] are similar to those given for 2-structures here. It is easy to see that $\mathcal{G}(D) = \mathcal{G}(\sigma_D)$, $\mathcal{D}(D, \Delta) = \mathcal{D}(\sigma_D, \sigma_\Delta)$, and $\mathcal{E}(D, \Delta) = \mathcal{E}(\sigma_D, \sigma_\Delta)$. Boussaïri et al. [4, 5] proved the following. If $D/\mathcal{G}(D)$ is prime, then $\mathcal{D}(D, \Delta)$ and $\mathcal{E}(D, \Delta)$ are not both connected.

The next result follows from Corollary 34 and Fact 32.

**Corollary 36.** Let $\sigma$ be a 2-structure such that $v(\sigma) \ge 4$. Suppose that $\sigma$ contains neither flags nor elements of $\Sigma_4$. If $\sigma$ is prime, then $\sigma$ is 3-forced.

*Proof.* Let $\tau$ be a 2-structure, which is 3-hemimorphic to $\sigma$. Clearly, $\sigma/\mathcal{G}(\sigma)$ is prime because $\sigma$ is prime. Since $\sigma$ does not contain elements of $\Sigma_4$, it follows from Corollary 34 that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are not both connected. By exchanging $\sigma$ and $\sigma^*$ if necessary, we can assume that $\mathcal{D}(\sigma, \tau)$ is disconnected. Let $C$ be any component of $\mathcal{D}(\sigma, \tau)$. Since $\sigma$ does not contain flags, it follows from Fact 32 that $V(C)$ is a module of $\sigma$. Lastly, since $\sigma$ is prime, $V(C)$ is a singleton. Consequently, the edge set of $\mathcal{D}(\sigma, \tau)$ is empty, which means $\sigma = \tau$. $\square$

**Remark 37.** For digraphs, Boussaïri et al. [4, 5] obtained the analogous result without forbidding the elements of $\Sigma_4$. Indeed, they proved that a prime digraph without flags is 3-forced. As seen in Example 29, it is also necessary to forbid the elements of $\Sigma_4$ for 2-structures.

# 4 Proofs of Theorems 8 and 10

**Proposition 38.** Let $\sigma$ be a 2-structure. Suppose that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices. If $\sigma$ is 3-forced, then $\sigma$ satisfies Statements (T1), (T2), and (T3) (see Theorem 8).

*Proof.* To begin, suppose that $G_\sigma$ is disconnected. Let $C$ be a component of $G_\sigma$. We consider the 2-structure $\tau$ defined on $V(\tau) = V(\sigma)$ as follows. Given distinct $v, w \in V(\tau)$,

$$ \tau(v, w) = \begin{cases} \sigma(w, v) & \text{if } \vec{\sigma}(\{v, w\}) \in V(C) \\ \sigma(v, w) & \text{otherwise.} \end{cases} $$

We verify that $\sigma$ and $\tau$ are 3-hemimorphic. Clearly, $\sigma$ and $\tau$ are 2-hemimorphic. Let $W \subseteq V(\sigma)$ satisfying $|W| = 3$. If $\tilde{L}_2(\sigma[W]) \subseteq V(C)$, then $\tau[W] = (\sigma[W])^*$. Furthermore, if $\tilde{L}_2(\sigma[W]) \cap V(C) = \emptyset$, then $\tau[W] = (\sigma[W])$. Therefore, suppose
The next result is an immediate consequence of Fact 30 and Lemma 33.

**Corollary 34.** Let $\sigma$ and $\tau$ be two 3-hemimorphic 2-structures. Suppose that $v(\sigma) \ge 4$. If $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected and if $\sigma/\mathcal{G}(\sigma)$ is prime, then there exists $W \subseteq V(\sigma)$ such that $\sigma[W]$ and $\tau[W]$ are isomorphic to an element of $\Sigma_4$ (see Notation 18).

**Remark 35.** Consider 3-hemimorphic digraphs $D$ and $\Delta$. The definitions of the modular partition $\mathcal{G}(D)$ and of the graphs $\mathcal{D}(D, \Delta)$ and $\mathcal{E}(D, \Delta)$ in [5] are similar to those given for 2-structures here. It is easy to see that $\mathcal{G}(D) = \mathcal{G}(\sigma_D)$, $\mathcal{D}(D, \Delta) = \mathcal{D}(\sigma_D, \sigma_\Delta)$, and $\mathcal{E}(D, \Delta) = \mathcal{E}(\sigma_D, \sigma_\Delta)$. Boussaïri et al. [4, 5] proved the following. If $D/\mathcal{G}(D)$ is prime, then $\mathcal{D}(D, \Delta)$ and $\mathcal{E}(D, \Delta)$ are not both connected.

The next result follows from Corollary 34 and Fact 32.

**Corollary 36.** Let $\sigma$ be a 2-structure such that $v(\sigma) \ge 4$. Suppose that $\sigma$ contains neither flags nor elements of $\Sigma_4$. If $\sigma$ is prime, then $\sigma$ is 3-forced.

*Proof.* Let $\tau$ be a 2-structure, which is 3-hemimorphic to $\sigma$. Clearly, $\sigma/\mathcal{G}(\sigma)$ is prime because $\sigma$ is prime. Since $\sigma$ does not contain elements of $\Sigma_4$, it follows from Corollary 34 that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are not both connected. By exchanging $\sigma$ and $\sigma^*$ if necessary, we can assume that $\mathcal{D}(\sigma, \tau)$ is disconnected. Let $C$ be any component of $\mathcal{D}(\sigma, \tau)$. Since $\sigma$ does not contain flags, it follows from Fact 32 that $V(C)$ is a module of $\sigma$. Lastly, since $\sigma$ is prime, $V(C)$ is a singleton. Consequently, the edge set of $\mathcal{D}(\sigma, \tau)$ is empty, which means $\sigma = \tau$. $\square$

**Remark 37.** For digraphs, Boussaïri et al. [4, 5] obtained the analogous result without forbidding the elements of $\Sigma_4$. Indeed, they proved that a prime digraph without flags is 3-forced. As seen in Example 29, it is also necessary to forbid the elements of $\Sigma_4$ for 2-structures.

# 4 Proofs of Theorems 8 and 10

**Proposition 38.** Let $\sigma$ be a 2-structure. Suppose that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices. If $\sigma$ is 3-forced, then $\sigma$ satisfies Statements (T1), (T2), and (T3) (see Theorem 8).

*Proof.* To begin, suppose that $G_\sigma$ is disconnected. Let $C$ be a component of $G_\sigma$. We consider the 2-structure $\tau$ defined on $V(\tau) = V(\sigma)$ as follows. Given distinct $v, w \in V(\tau)$,

$$ \tau(v, w) = \begin{cases} \sigma(w, v) & \text{if } \vec{\sigma}(\{v, w\}) \in V(C) \\ \sigma(v, w) & \text{otherwise.} \end{cases} $$

We verify that $\sigma$ and $\tau$ are 3-hemimorphic. Clearly, $\sigma$ and $\tau$ are 2-hemimorphic. Let $W \subseteq V(\sigma)$ satisfying $|W| = 3$. If $\tilde{L}_2(\sigma[W]) \subseteq V(C)$, then $\tau[W] = (\sigma[W])^*$. Furthermore, if $\tilde{L}_2(\sigma[W]) \cap V(C) = \emptyset$, then $\tau[W] = (\sigma[W])$. Therefore, suppose
that there exist $p \in \tilde{L}_2(\sigma[W]) \cap V(C)$ and $q \in (\tilde{L}_2(\sigma[W]) \setminus V(C))$. By definition of $G_\sigma$, $\sigma[W]$ is decomposable. It follows that $\tilde{L}_2(\sigma[W]) = \{p, q\}$. Consider distinct $v, w \in W$ such that $\{v, w\}$ is a nontrivial module of $\sigma[W]$. If $\tilde{\sigma}(\{v, w\}) = p$, then $\tau[W]$ is isomorphic to $\sigma[W]$. Moreover, if $\tilde{\sigma}(\{v, w\}) = q$, then $\tau[W]$ is isomorphic to $(\sigma[W])^*$. Consequently, $\sigma$ and $\tau$ are 3-hemimorphic. It follows that $\sigma$ is not 3-forced. In what follows, we suppose that Statement (T1) holds.

To continue, suppose that there exists $M \in \mathscr{G}(\sigma)$ such that $E_2(\sigma[M]) \neq \emptyset$. By Fact 23, $\sigma$ and $\mathrm{Inv}(\sigma, M)$ are 3-hemimorphic. Since $E_2(\sigma[M]) \neq \emptyset$, $\mathrm{Inv}(\sigma, M) \neq \sigma$. Let $v \in V(\sigma) \setminus M$. Since $(V(\sigma), E_2(\sigma))$ does not have isolated vertices, there exists $w \in V(\sigma) \setminus \{v\}$ such that $\{v, w\} \in E_2(\sigma)$. Since $\{v, w\} \setminus M \neq \emptyset$, $\mathrm{Inv}(\sigma, M) \neq \sigma^*$. It follows that $\sigma$ is not 3-forced. In what follows, we suppose that Statement (T2) holds.

Lastly, suppose that $|\mathscr{G}(\sigma)| \ge 3$ but $\sigma/\mathscr{G}(\sigma)$ is not prime. By Theorem 4, $\sigma/\mathscr{G}(\sigma)$ is constant or linear. Let $M \in \sigma/\mathscr{G}(\sigma)$. Consider $v \in M$. Since $(V(\sigma), E_2(\sigma))$ does not have isolated vertices, there exists $w \in V(\sigma) \setminus \{v\}$ such that $\{v, w\} \in E_2(\sigma)$. Furthermore, since Statement (T2) holds, $w \notin M$. It follows that $\sigma/\mathscr{G}(\sigma)$ is not constant, so $\sigma/\mathscr{G}(\sigma)$ is linear. Let $M_0$ and $M_1$ be the first two elements of $\sigma/\mathscr{G}(\sigma)$. Clearly, $M_0 \cup M_1$ is a module of $\sigma$. By Fact 23, $\sigma$ and $\mathrm{Inv}(\sigma, M_0 \cup M_1)$ are 3-hemimorphic. For $v_0 \in M_0$ and $v_1 \in M_1$, we have $\{v_0, v_1\} \in E_2(\sigma)$, and hence $\mathrm{Inv}(\sigma, M) \neq \sigma$. Since $|\mathscr{G}(\sigma)| \ge 3$, there exists $v \in V(\sigma) \setminus (M_0 \cup M_1)$. We obtain $\{v_0, v\} \in E_2(\sigma)$, and hence $\mathrm{Inv}(\sigma, M) \neq \sigma^*$. It follows that $\sigma$ is not 3-forced. Consequently, Statement (T3) holds. $\square$

**Proposition 39.** Let $\sigma$ be a prime 2-structure. Suppose that $\sigma = \vec{\sigma}$. If $\sigma$ satisfies Statement (T1), then $\sigma$ is 3-forced.

*Proof.* Consider a 2-structure $\tau$ which is 3-hemimorphic to $\sigma$. To begin, suppose that $|\tilde{L}_2(\sigma)| = 1$. Since $\sigma = \vec{\sigma}$, $\sigma$ does not contain flags. Furthermore, since $|\tilde{L}_2(\sigma)| = 1$, $\sigma$ does not contain elements of $\Sigma_4$. It follows from Corollary 36 that $\tau = \sigma$ or $\sigma^*$.

Now, suppose that $|\tilde{L}_2(\sigma)| \ge 2$. Since $G_\sigma$ is connected by Statement (T1), there exists $X \subseteq V(\sigma)$ such that $|X| = 3$ and $\sigma[X]$ is prime. By Lemma 16, there exist elements $y_0, \dots, y_{v(\sigma)-4}$ of $V(\sigma) \setminus X$ such that Statements (S1), (S2), and (S3) hold. For a contradiction, suppose that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected. By applying several times Lemma 33, we obtain that $\mathcal{D}(\sigma[X \cup \{y_0\}], \tau[X \cup \{y_0\}])$ and $\mathcal{E}(\sigma[X \cup \{y_0\}], \tau[X \cup \{y_0\}])$ are both connected. By Fact 30, $\sigma[X \cup \{y_0\}]$ is isomorphic to an element of $\Sigma_4$ (see Notation 18). By Claim 19, $\sigma[X \cup \{y_0\}]$ is critical, which is impossible because $\sigma[X]$ is prime. Consequently, $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are not both connected. By exchanging $\tau$ and $\tau^*$ if necessary, we can assume that $\mathcal{D}(\sigma, \tau)$ is disconnected. As shown at the end of the proof of Corollary 36, we obtain $\sigma = \tau$. $\square$

The next result is an immediate consequence of Propositions 38 and 39.

**Corollary 40.** Let $\sigma$ be a prime 2-structure. Suppose that $\sigma = \vec{\sigma}$. The 2-structure $\sigma$ is 3-forced if and only if $\sigma$ satisfies Statement (T1).
that there exist $p \in \tilde{L}_2(\sigma[W]) \cap V(C)$ and $q \in (\tilde{L}_2(\sigma[W]) \setminus V(C))$. By definition of $G_\sigma$, $\sigma[W]$ is decomposable. It follows that $\tilde{L}_2(\sigma[W]) = \{p, q\}$. Consider distinct $v, w \in W$ such that $\{v, w\}$ is a nontrivial module of $\sigma[W]$. If $\tilde{\sigma}(\{v, w\}) = p$, then $\tau[W]$ is isomorphic to $\sigma[W]$. Moreover, if $\tilde{\sigma}(\{v, w\}) = q$, then $\tau[W]$ is isomorphic to $(\sigma[W])^*$. Consequently, $\sigma$ and $\tau$ are 3-hemimorphic. It follows that $\sigma$ is not 3-forced. In what follows, we suppose that Statement (T1) holds.

To continue, suppose that there exists $M \in \mathscr{G}(\sigma)$ such that $E_2(\sigma[M]) \neq \emptyset$. By Fact 23, $\sigma$ and $\mathrm{Inv}(\sigma, M)$ are 3-hemimorphic. Since $E_2(\sigma[M]) \neq \emptyset$, $\mathrm{Inv}(\sigma, M) \neq \sigma$. Let $v \in V(\sigma) \setminus M$. Since $(V(\sigma), E_2(\sigma))$ does not have isolated vertices, there exists $w \in V(\sigma) \setminus \{v\}$ such that $\{v, w\} \in E_2(\sigma)$. Since $\{v, w\} \setminus M \neq \emptyset$, $\mathrm{Inv}(\sigma, M) \neq \sigma^*$. It follows that $\sigma$ is not 3-forced. In what follows, we suppose that Statement (T2) holds.

Lastly, suppose that $|\mathscr{G}(\sigma)| \ge 3$ but $\sigma/\mathscr{G}(\sigma)$ is not prime. By Theorem 4, $\sigma/\mathscr{G}(\sigma)$ is constant or linear. Let $M \in \sigma/\mathscr{G}(\sigma)$. Consider $v \in M$. Since $(V(\sigma), E_2(\sigma))$ does not have isolated vertices, there exists $w \in V(\sigma) \setminus \{v\}$ such that $\{v, w\} \in E_2(\sigma)$. Furthermore, since Statement (T2) holds, $w \notin M$. It follows that $\sigma/\mathscr{G}(\sigma)$ is not constant, so $\sigma/\mathscr{G}(\sigma)$ is linear. Let $M_0$ and $M_1$ be the first two elements of $\sigma/\mathscr{G}(\sigma)$. Clearly, $M_0 \cup M_1$ is a module of $\sigma$. By Fact 23, $\sigma$ and $\mathrm{Inv}(\sigma, M_0 \cup M_1)$ are 3-hemimorphic. For $v_0 \in M_0$ and $v_1 \in M_1$, we have $\{v_0, v_1\} \in E_2(\sigma)$, and hence $\mathrm{Inv}(\sigma, M) \neq \sigma$. Since $|\mathscr{G}(\sigma)| \ge 3$, there exists $v \in V(\sigma) \setminus (M_0 \cup M_1)$. We obtain $\{v_0, v\} \in E_2(\sigma)$, and hence $\mathrm{Inv}(\sigma, M) \neq \sigma^*$. It follows that $\sigma$ is not 3-forced. Consequently, Statement (T3) holds. $\square$

**Proposition 39.** Let $\sigma$ be a prime 2-structure. Suppose that $\sigma = \vec{\sigma}$. If $\sigma$ satisfies Statement (T1), then $\sigma$ is 3-forced.

*Proof.* Consider a 2-structure $\tau$ which is 3-hemimorphic to $\sigma$. To begin, suppose that $|\tilde{L}_2(\sigma)| = 1$. Since $\sigma = \vec{\sigma}$, $\sigma$ does not contain flags. Furthermore, since $|\tilde{L}_2(\sigma)| = 1$, $\sigma$ does not contain elements of $\Sigma_4$. It follows from Corollary 36 that $\tau = \sigma$ or $\sigma^*$.

Now, suppose that $|\tilde{L}_2(\sigma)| \ge 2$. Since $G_\sigma$ is connected by Statement (T1), there exists $X \subseteq V(\sigma)$ such that $|X| = 3$ and $\sigma[X]$ is prime. By Lemma 16, there exist elements $y_0, \dots, y_{v(\sigma)-4}$ of $V(\sigma) \setminus X$ such that Statements (S1), (S2), and (S3) hold. For a contradiction, suppose that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected. By applying several times Lemma 33, we obtain that $\mathcal{D}(\sigma[X \cup \{y_0\}], \tau[X \cup \{y_0\}])$ and $\mathcal{E}(\sigma[X \cup \{y_0\}], \tau[X \cup \{y_0\}])$ are both connected. By Fact 30, $\sigma[X \cup \{y_0\}]$ is isomorphic to an element of $\Sigma_4$ (see Notation 18). By Claim 19, $\sigma[X \cup \{y_0\}]$ is critical, which is impossible because $\sigma[X]$ is prime. Consequently, $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are not both connected. By exchanging $\tau$ and $\tau^*$ if necessary, we can assume that $\mathcal{D}(\sigma, \tau)$ is disconnected. As shown at the end of the proof of Corollary 36, we obtain $\sigma = \tau$. $\square$

The next result is an immediate consequence of Propositions 38 and 39.

**Corollary 40.** Let $\sigma$ be a prime 2-structure. Suppose that $\sigma = \vec{\sigma}$. The 2-structure $\sigma$ is 3-forced if and only if $\sigma$ satisfies Statement (T1).
**Problem 41.** A 2-structure $\sigma$ is said to be *asymmetric* if $\tilde{L}_1(\sigma) = \emptyset$. Describe the structural form of a prime asymmetric 2-structure $\sigma$ such that there exists a 2-structure $\tau$ satisfying

* $\sigma$ and $\tau$ are 3-hemimorphic;

* $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected.

As seen in Example 29, $\gamma_{2n}$ is such a 2-structure.

*Proof of Theorem 8.* To begin, suppose that $\sigma$ is 3-forced. By Proposition 38, $\sigma$ satisfies Statements (T1), (T2), and (T3). Conversely, suppose that $\sigma$ satisfies Statements (T1), (T2), and (T3). If $\sigma$ is prime, then it follows from Proposition 39 that $\sigma$ is 3-forced. Hence, suppose that $\sigma$ is decomposable. Consider a 2-structure $\tau$ which is 3-hemimorphic to $\sigma$. Since $\sigma$ satisfies Statement (T2), it follows from Fact 24 that $\mathcal{G}(\sigma)$ is a modular partition of $\tau$ as well.

To continue, we show that for each $M \in \mathcal{G}(\sigma)$, there exists $N \in \mathcal{G}(\sigma) \setminus \{M\}$ such that

$$ \{x, y\} \in E_2(\sigma) \qquad (6) $$

for any $x \in M$ and $y \in N$. Let $M \in \mathcal{G}(\sigma)$. Consider $v \in M$. Since $(V(\sigma), E_2(\sigma))$ does not have isolated vertices, there exists $w \in V(\sigma) \setminus \{v\}$ such that $\{v, w\} \in E_2(\sigma)$. Furthermore, since Statement (T2) holds, $w \notin M$. By denoting by $N$ the element of $\mathcal{G}(\sigma)$ containing $w$, we obtain that (6) holds.

We conclude as follows. First, suppose that $|\mathcal{G}(\sigma)| = 2$. It follows from (6) that $\sigma/\mathcal{G}(\sigma)$ is linear. Since $\sigma$ and $\tau$ are 3-hemimorphic, we have $E_2(\tau[M]) = \emptyset$ for each $M \in \mathcal{G}(\sigma)$. Lastly, since $\mathcal{G}(\sigma)$ is a modular partition of $\tau$, we obtain $\tau = \sigma$ or $\sigma^*$.

Second, suppose that $|\mathcal{G}(\sigma)| \ge 3$. Since $\sigma$ satisfies Statement (T3), $\sigma/\mathcal{G}(\sigma)$ is prime. Consider the set $\mathcal{T}$ of $X \subseteq V(\sigma)$ such that $|X \cap M| = 1$ for each $M \in \mathcal{G}(\sigma)$. For every $X \in \mathcal{T}$, we verify that

$$ \tau[X] = \sigma[X] \text{ or } (\sigma[X])^*. \qquad (7) $$

Let $X \in \mathcal{T}$. Since $\sigma/\mathcal{G}(\sigma)$ is prime, $\sigma[X]$ is prime. Since $\sigma$ satisfies Statements (T1), (T2), and (T3), $\sigma[X]$ satisfies Statement (T1). Since $\sigma[X]$ and $\tau[X]$ are 3-hemimorphic too, it follows from Proposition 39 that $\tau[X] = \sigma[X]$ or $(\sigma[X])^*$. Consequently, (7) holds. Finally, by (6), there exist distinct $M, N \in \mathcal{G}(\sigma)$ such that $\{x, y\} \in E_2(\sigma)$ for any $x \in M$ and $y \in N$. Since $\mathcal{G}(\sigma)$ is a modular partition of $\tau$, we obtain

for any $x \in M$ and $y \in N$, $xy \in E(\mathcal{D}(\sigma, \tau))$

or

for any $x \in M$ and $y \in N$, $xy \in E(\mathcal{E}(\sigma, \tau))$.

By exchanging $\tau$ and $\tau^*$ if necessary, we can assume that $xy \in E(\mathcal{E}(\sigma, \tau))$ for any $x \in M$ and $y \in N$. For every $X \in \mathcal{T}$, it follows from (7) that $\tau[X] = \sigma[X]$. We obtain $\sigma = \tau$. $\square$

<figure><img src="image_3.png" /></figure>
**Problem 41.** A 2-structure $\sigma$ is said to be *asymmetric* if $\tilde{L}_1(\sigma) = \emptyset$. Describe the structural form of a prime asymmetric 2-structure $\sigma$ such that there exists a 2-structure $\tau$ satisfying

* $\sigma$ and $\tau$ are 3-hemimorphic;

* $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected.

As seen in Example 29, $\gamma_{2n}$ is such a 2-structure.

*Proof of Theorem 8.* To begin, suppose that $\sigma$ is 3-forced. By Proposition 38, $\sigma$ satisfies Statements (T1), (T2), and (T3). Conversely, suppose that $\sigma$ satisfies Statements (T1), (T2), and (T3). If $\sigma$ is prime, then it follows from Proposition 39 that $\sigma$ is 3-forced. Hence, suppose that $\sigma$ is decomposable. Consider a 2-structure $\tau$ which is 3-hemimorphic to $\sigma$. Since $\sigma$ satisfies Statement (T2), it follows from Fact 24 that $\mathcal{G}(\sigma)$ is a modular partition of $\tau$ as well.

To continue, we show that for each $M \in \mathcal{G}(\sigma)$, there exists $N \in \mathcal{G}(\sigma) \setminus \{M\}$ such that

$$ \{x, y\} \in E_2(\sigma) \qquad (6) $$

for any $x \in M$ and $y \in N$. Let $M \in \mathcal{G}(\sigma)$. Consider $v \in M$. Since $(V(\sigma), E_2(\sigma))$ does not have isolated vertices, there exists $w \in V(\sigma) \setminus \{v\}$ such that $\{v, w\} \in E_2(\sigma)$. Furthermore, since Statement (T2) holds, $w \notin M$. By denoting by $N$ the element of $\mathcal{G}(\sigma)$ containing $w$, we obtain that (6) holds.

We conclude as follows. First, suppose that $|\mathcal{G}(\sigma)| = 2$. It follows from (6) that $\sigma/\mathcal{G}(\sigma)$ is linear. Since $\sigma$ and $\tau$ are 3-hemimorphic, we have $E_2(\tau[M]) = \emptyset$ for each $M \in \mathcal{G}(\sigma)$. Lastly, since $\mathcal{G}(\sigma)$ is a modular partition of $\tau$, we obtain $\tau = \sigma$ or $\sigma^*$.

Second, suppose that $|\mathcal{G}(\sigma)| \ge 3$. Since $\sigma$ satisfies Statement (T3), $\sigma/\mathcal{G}(\sigma)$ is prime. Consider the set $\mathcal{T}$ of $X \subseteq V(\sigma)$ such that $|X \cap M| = 1$ for each $M \in \mathcal{G}(\sigma)$. For every $X \in \mathcal{T}$, we verify that

$$ \tau[X] = \sigma[X] \text{ or } (\sigma[X])^*. \qquad (7) $$

Let $X \in \mathcal{T}$. Since $\sigma/\mathcal{G}(\sigma)$ is prime, $\sigma[X]$ is prime. Since $\sigma$ satisfies Statements (T1), (T2), and (T3), $\sigma[X]$ satisfies Statement (T1). Since $\sigma[X]$ and $\tau[X]$ are 3-hemimorphic too, it follows from Proposition 39 that $\tau[X] = \sigma[X]$ or $(\sigma[X])^*$. Consequently, (7) holds. Finally, by (6), there exist distinct $M, N \in \mathcal{G}(\sigma)$ such that $\{x, y\} \in E_2(\sigma)$ for any $x \in M$ and $y \in N$. Since $\mathcal{G}(\sigma)$ is a modular partition of $\tau$, we obtain

for any $x \in M$ and $y \in N$, $xy \in E(\mathcal{D}(\sigma, \tau))$

or

for any $x \in M$ and $y \in N$, $xy \in E(\mathcal{E}(\sigma, \tau))$.

By exchanging $\tau$ and $\tau^*$ if necessary, we can assume that $xy \in E(\mathcal{E}(\sigma, \tau))$ for any $x \in M$ and $y \in N$. For every $X \in \mathcal{T}$, it follows from (7) that $\tau[X] = \sigma[X]$. We obtain $\sigma = \tau$. $\square$
An equivalent statement of Theorem 8 follows.

**Theorem 42.** Let $\sigma$ be a 2-structure. Suppose that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices. The 2-structure $\sigma$ is 3-forced if and only if the following two statements hold

(T1) $G_\sigma$ is connected;

(T4) for each nontrivial module $M$ of $\sigma$, $E_2(\sigma[M]) = \emptyset$.

We conclude with the proof of Theorem 10.

*Proof of Theorem 10.* Suppose that $\sigma$ is prime and $(V(\sigma), E_2(\sigma))$ is connected. If $v(\sigma) = 3$, then it suffices to apply Fact 25. Hence, suppose that $v(\sigma) \ge 4$. Consider a 2-structure $\tau$ which is 4-hemimorphic to $\sigma$. We have to show that $\tau = \sigma$ or $\sigma^*$.

For a contradiction, suppose that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected. By applying several times Lemma 33, we obtain $X \subseteq V(\sigma)$ satisfying

* $|X| = 4$;

* $\sigma[X]/\mathcal{G}(\sigma[X])$ is prime;

* $\mathcal{D}(\sigma[X], \tau[X])$ and $\mathcal{E}(\sigma[X], \tau[X])$ are both connected.

By Fact 30, there exists an isomorphism $\varphi$ from $\sigma[X]$ onto an element of $\Sigma_4$ (see Notation 18), which is also an isomorphism from $\mathcal{D}(\sigma[X], \tau[X])$ onto $G_4$ (see Example 20). As already noted in Example 29, $\sigma[X]$ is never isomorphic to either $\tau[X]$ or $(\tau[X])^*$, which contradicts the fact that $\sigma$ and $\tau$ are 4-hemimorphic. Consequently, $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are not both connected.

By exchanging $\sigma$ and $\sigma^*$ if necessary, we can assume that $\mathcal{D}(\sigma, \tau)$ is disconnected. Consider a component $C$ of $\mathcal{D}(\sigma, \tau)$. We verify that $V(C)$ is a module of $\sigma$. Let $v \in V(\sigma) \setminus V(C)$. We distinguish the following two cases.

1. There exists $x \in V(C)$ such that $\{x, v\} \in E_2(\sigma)$. Since $v \notin V(C)$, we have $xv \in E(\mathcal{E}(\sigma, \tau))$. Let $y \in V(C)$ such that $xy \in E(\mathcal{D}(\sigma, \tau))$. We prove that

$$ \sigma(x, v) = \sigma(y, v). $$

It follows from Fact 24 that either $\{x, y\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$ or $\{x, v\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$. If $\{x, v\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$, then $yv \in E(\mathcal{D}(\sigma, \tau))$, which contradicts the fact that $C$ is a component of $\mathcal{D}(\sigma, \tau)$. Hence, $\{x, y\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$. Thus, we have $\sigma(x, v) = \sigma(y, v)$. Now, by considering $z \in V(C)$ such that $yz \in E(\mathcal{D}(\sigma, \tau))$, we obtain in the same manner that $\sigma(y, v) = \sigma(z, v)$, and hence $\sigma(x, v) = \sigma(z, v)$. Since $C$ is a component of $\mathcal{D}(\sigma, \tau)$, we obtain $\sigma(x, v) = \sigma(t, v)$ for every $t \in V(C)$.
An equivalent statement of Theorem 8 follows.

**Theorem 42.** Let $\sigma$ be a 2-structure. Suppose that $\sigma = \vec{\sigma}$ and $(V(\sigma), E_2(\sigma))$ does not have isolated vertices. The 2-structure $\sigma$ is 3-forced if and only if the following two statements hold

(T1) $G_\sigma$ is connected;

(T4) for each nontrivial module $M$ of $\sigma$, $E_2(\sigma[M]) = \emptyset$.

We conclude with the proof of Theorem 10.

*Proof of Theorem 10.* Suppose that $\sigma$ is prime and $(V(\sigma), E_2(\sigma))$ is connected. If $v(\sigma) = 3$, then it suffices to apply Fact 25. Hence, suppose that $v(\sigma) \ge 4$. Consider a 2-structure $\tau$ which is 4-hemimorphic to $\sigma$. We have to show that $\tau = \sigma$ or $\sigma^*$.

For a contradiction, suppose that $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are both connected. By applying several times Lemma 33, we obtain $X \subseteq V(\sigma)$ satisfying

* $|X| = 4$;

* $\sigma[X]/\mathcal{G}(\sigma[X])$ is prime;

* $\mathcal{D}(\sigma[X], \tau[X])$ and $\mathcal{E}(\sigma[X], \tau[X])$ are both connected.

By Fact 30, there exists an isomorphism $\varphi$ from $\sigma[X]$ onto an element of $\Sigma_4$ (see Notation 18), which is also an isomorphism from $\mathcal{D}(\sigma[X], \tau[X])$ onto $G_4$ (see Example 20). As already noted in Example 29, $\sigma[X]$ is never isomorphic to either $\tau[X]$ or $(\tau[X])^*$, which contradicts the fact that $\sigma$ and $\tau$ are 4-hemimorphic. Consequently, $\mathcal{D}(\sigma, \tau)$ and $\mathcal{E}(\sigma, \tau)$ are not both connected.

By exchanging $\sigma$ and $\sigma^*$ if necessary, we can assume that $\mathcal{D}(\sigma, \tau)$ is disconnected. Consider a component $C$ of $\mathcal{D}(\sigma, \tau)$. We verify that $V(C)$ is a module of $\sigma$. Let $v \in V(\sigma) \setminus V(C)$. We distinguish the following two cases.

1. There exists $x \in V(C)$ such that $\{x, v\} \in E_2(\sigma)$. Since $v \notin V(C)$, we have $xv \in E(\mathcal{E}(\sigma, \tau))$. Let $y \in V(C)$ such that $xy \in E(\mathcal{D}(\sigma, \tau))$. We prove that

$$ \sigma(x, v) = \sigma(y, v). $$

It follows from Fact 24 that either $\{x, y\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$ or $\{x, v\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$. If $\{x, v\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$, then $yv \in E(\mathcal{D}(\sigma, \tau))$, which contradicts the fact that $C$ is a component of $\mathcal{D}(\sigma, \tau)$. Hence, $\{x, y\}$ is a module of $\sigma[\{x, y, v\}]$ and $\tau[\{x, y, v\}]$. Thus, we have $\sigma(x, v) = \sigma(y, v)$. Now, by considering $z \in V(C)$ such that $yz \in E(\mathcal{D}(\sigma, \tau))$, we obtain in the same manner that $\sigma(y, v) = \sigma(z, v)$, and hence $\sigma(x, v) = \sigma(z, v)$. Since $C$ is a component of $\mathcal{D}(\sigma, \tau)$, we obtain $\sigma(x, v) = \sigma(t, v)$ for every $t \in V(C)$.
2. For every $x \in V(C)$, $\{x, v\} \in E_1(\sigma)$. Since $(V(\sigma), E_2(\sigma))$ is connected, there exists $y \in V(C)$ and $w \in V(\sigma) \setminus V(C)$ such that $\{y, w\} \in E_2(\sigma)$. By the first case above, we have $\sigma(y, w) = \sigma(t, w)$ for every $t \in V(C)$. Let $z \in V(C)$ such that $yz \in E(\mathcal{D}(\sigma, \tau))$. We have $\sigma(y, w) = \sigma(z, w)$ and $zw \in E(\mathcal{E}(\sigma, \tau))$. Since $\sigma$ and $\tau$ are 4-hemimorphic, there exists an isomorphism $f$ from $\sigma[\{y, z, v, w\}]$ onto $\tau[\{y, z, v, w\}]$ or $(\tau[\{y, z, v, w\}])^*$. Since $v$ is the unique element of $\{y, z, v, w\}$ such that

$$|\{t \in \{y, z, v, w\} : \{t, v\} \in E_1(\sigma)\}| \geq 2,$$

we have $f(v) = v$. We obtain $f = (yz)$ or $(ywz)$. In both cases, we have $\sigma(y, v) = \sigma(z, v)$. We conclude as in the first case above by using the fact that $C$ is a component of $\mathcal{D}(\sigma, \tau)$.

It follows that $V(C)$ is a module of $\sigma$. Since $\sigma$ is prime, $V(C)$ is a singleton. Consequently, the edge set of $\mathcal{D}(\sigma, \tau)$ is empty, which means $\sigma = \tau$. $\square$

## Acknowledgements

The authors thank the referee for his constructive suggestions that allow for notable improvements to the manuscript.

## References

[1] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839-2846.

[2] A. Boussaïri, Décomposabilité, Dualité et Groupes Finis, PhD Dissertation (unpublished), University Lyon I, 1995.

[3] A. Boussaïri, P. Ille, Different duality theorems, Ars Combin. 112 (2013) 14-33.

[4] A. Boussaïri, P. Ille, G. Lopez, S. Thomassé, Hypomorphie et inversion locale entre graphes, C.R. Acad. Sci. Paris Sér. I Math. 317 (1993) 125-128.

[5] A. Boussaïri, P. Ille, G. Lopez, S. Thomassé, The $C_3$-structure of the tournaments, Discrete Math. 277 (2004) 29-43.

[6] J. Dammak, La dualité dans la demi-reconstruction des relations binaires finies, C. R. Acad. Sci. Paris Sér. I Math. 327 (1998) 861-864.

[7] A. Ehrenfeucht, T. Harju, G. Rozenberg, The Theory of 2-Structures, A Framework for Decomposition and Transformation of Graphs, World Scientific, Singapore, 1999, xvi+290 pp.
2. For every $x \in V(C)$, $\{x, v\} \in E_1(\sigma)$. Since $(V(\sigma), E_2(\sigma))$ is connected, there exists $y \in V(C)$ and $w \in V(\sigma) \setminus V(C)$ such that $\{y, w\} \in E_2(\sigma)$. By the first case above, we have $\sigma(y, w) = \sigma(t, w)$ for every $t \in V(C)$. Let $z \in V(C)$ such that $yz \in E(\mathcal{D}(\sigma, \tau))$. We have $\sigma(y, w) = \sigma(z, w)$ and $zw \in E(\mathcal{E}(\sigma, \tau))$. Since $\sigma$ and $\tau$ are 4-hemimorphic, there exists an isomorphism $f$ from $\sigma[\{y, z, v, w\}]$ onto $\tau[\{y, z, v, w\}]$ or $(\tau[\{y, z, v, w\}])^*$. Since $v$ is the unique element of $\{y, z, v, w\}$ such that

$$|\{t \in \{y, z, v, w\} : \{t, v\} \in E_1(\sigma)\}| \geq 2,$$

we have $f(v) = v$. We obtain $f = (yz)$ or $(ywz)$. In both cases, we have $\sigma(y, v) = \sigma(z, v)$. We conclude as in the first case above by using the fact that $C$ is a component of $\mathcal{D}(\sigma, \tau)$.

It follows that $V(C)$ is a module of $\sigma$. Since $\sigma$ is prime, $V(C)$ is a singleton. Consequently, the edge set of $\mathcal{D}(\sigma, \tau)$ is empty, which means $\sigma = \tau$. $\square$

## Acknowledgements

The authors thank the referee for his constructive suggestions that allow for notable improvements to the manuscript.

## References

[1] Y. Boudabbous, P. Ille, Indecomposability graph and critical vertices of an indecomposable graph, Discrete Math. 309 (2009) 2839–2846.

[2] A. Boussaïri, Décomposabilité, Dualité et Groupes Finis, PhD Dissertation (unpublished), University Lyon I, 1995.

[3] A. Boussaïri, P. Ille, Different duality theorems, Ars Combin. 112 (2013) 14–33.

[4] A. Boussaïri, P. Ille, G. Lopez, S. Thomassé, Hypomorphie et inversion locale entre graphes, C.R. Acad. Sci. Paris Sér. I Math. 317 (1993) 125–128.

[5] A. Boussaïri, P. Ille, G. Lopez, S. Thomassé, The $C_3$-structure of the tournaments, Discrete Math. 277 (2004) 29–43.

[6] J. Dammak, La dualité dans la demi-reconstruction des relations binaires finies, C. R. Acad. Sci. Paris Sér. I Math. 327 (1998) 861–864.

[7] A. Ehrenfeucht, T. Harju, G. Rozenberg, The Theory of 2-Structures, A Framework for Decomposition and Transformation of Graphs, World Scientific, Singapore, 1999, xvi+290 pp.
[8] T. Gallai, Transitiv orientierbare Graphen, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66.

[9] J.-G. Hagendorf, G. Lopez, La demi-reconstructibilité des relations binaires de cardinal < 12, C. R. Acad. Sci. Paris Sér. I Math. 317 (1993) 7–12.

[10] P. Ille, La décomposition intervallaire des structures binaires, La Gazette des Mathématiciens 104 (2005) 39–58.

[11] P. Ille, Prime 2-structures, to appear as a special issue of Contrib. Discrete Math, 2022, ii+244 pp.

[12] P. Ille, R. Woodrow, Weakly partitive families on infinite sets, Contrib. Discrete Math. 4 (2009) 54–80.

[13] F. Maffray, M. Preissmann, A translation of Tibor Gallai's paper: Transitiv orientierbare Graphen, in: J.L. Ramirez-Alfonsin and B.A. Reed (Eds.), Perfect Graphs, Wiley, New York, 2001, pp. 25–66.

[14] J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Math. 113 (1993) 191–205.
[8] T. Gallai, *Transitiv orientierbare Graphen*, Acta Math. Acad. Sci. Hungar. 18 (1967) 25–66.

[9] J.-G. Hagendorf, G. Lopez, *La demi-reconstructibilité des relations binaires de cardinal < 12*, C. R. Acad. Sci. Paris Sér. I Math. 317 (1993) 7–12.

[10] P. Ille, *La décomposition intervallaire des structures binaires*, La Gazette des Mathématiciens 104 (2005) 39–58.

[11] P. Ille, *Prime 2-structures, to appear as a special issue of Contrib. Discrete Math*, 2022, ii+244 pp.

[12] P. Ille, R. Woodrow, *Weakly partitive families on infinite sets*, Contrib. Discrete Math. 4 (2009) 54–80.

[13] F. Maffray, M. Preissmann, *A translation of Tibor Gallai's paper: Transitiv orientierbare Graphen*, in: J.L. Ramirez-Alfonsin and B.A. Reed (Eds.), *Perfect Graphs*, Wiley, New York, 2001, pp. 25–66.

[14] J.H. Schmerl, W.T. Trotter, *Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures*, Discrete Math. 113 (1993) 191–205.