Proof. The forward direction follows from the fact that the projection of an independence modelcontains all and only the pairwise independence statements that hold in a graph. For the reverse direction we assume that \(\text{\rmfamily\upshape Pairwise}(I)=\text{\rmfamily\upshape Pairwise}(I')\). Assume that the claim does not hold. In that case there must be an \(\left( A,B,C \right)\) such that either (i) \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {C}\) and \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I'}\ {B}\ |\ {C}\) or (ii) \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {B}\ |\ {C}\) and \({A} \perp\!\!\!\!\perp_{I'} {B}\ |\ {C}\). Without loss of generality, assume (i). From decomposition we have \({a} \perp\!\!\!\!\perp_{I} {b}\ |\ {C}\) for \(a\in A\) and \(b\in B\). From pairwise equivalence, we have \({a} \perp\!\!\!\!\perp_{I'} {b}\ |\ {C}\) for \(a\in A\) and \(b\in B\). Finally, from composition we have \({A} \perp\!\!\!\!\perp_{I'} {B}\ |\ {C}\). Thus we have a contradiction and the claim holds. ◻

Proof. The forward direction follows from the fact that the projection of an independence modelcontains all and only the pairwise independence statements that hold in a graph. The reverse direction follows from the fact that every non-pairwise dependence statement \({A} \perp\!\!\!\!\perp_{} {B}\ |\ {C}\) that holds in a independence model\(I\) is a deterministic function of \(\text{\rmfamily\upshape Pairwise}(I)\) and the trivial independence function and the contrapositive versions of the symmetry and decomposition properties applied to the set of pairwise dependent statements that hold in \(I\). ◻

Proof. Let \(I=\left( {\cal O},T \right)\) and \(L_1, L_2,S_1,S_2\) be disjoint sets of \({\cal O}\).

We define useful projections for sets of tests \(T \subseteq {\cal T}_{{\cal O}}\) for object domain \({\cal O}\).

\[\text{\rmfamily\upshape C}_S(T)= \{\, {\left( A,B,C \right)}\in {\tests_{{\cal O}\setminus S}}\ | \ {\left( A,B,C\cup S \right) \in T \wedge (A\cup B \cup C)\cap S = \emptyset} \,\}\] \[\text{\rmfamily\upshape M}_L(T)= \{\, {\left( A,B,D \right)}\in {\tests_{{\cal O}\setminus L}}\ | \ {\left( A,B,D \right) \in T \wedge (A\cup B \cup D) \cap L = \emptyset} \,\}\]

These projections allow us to provide an alternative definition of the conditional projectionprojection: \[\text{\rmfamily\upshape E}^{L}_{S}(I)= \left( {\cal O}\setminus (L \cup S), \text{\rmfamily\upshape C}_S(T) \cap \text{\rmfamily\upshape M}_L(T) \right).\]

The first property in the proposition then follows from the fact that \(\text{\rmfamily\upshape C}_\emptyset(T)=\text{\rmfamily\upshape M}_\emptyset(T)=T\) and basic set manipulation.

Next we define \(\cap\) for independence models by lifting \(\cap\) on sets to tuples. In particular, \[\left( {\cal O},T \right)\cap \left( {\cal O}',T' \right)=\left( {\cal O}\cap {\cal O}', T \cap T' \right).\] This allows us to relate the composition of conditional projections to intersection for disjoint subsets \(L_1,L_2,S_1,S_2\) of \({\cal O}\) as follows: \[\text{\rmfamily\upshape E}^{L_1}_{S_1}\circ \text{\rmfamily\upshape E}^{L_2}_{S_2}=\text{\rmfamily\upshape E}^{L_1}_{S_1}\cap \text{\rmfamily\upshape E}^{L_2}_{S_2}.\]

Properties (2) and (3) from the proposition then follows from basic properties of sets. ◻

Proof. Follows from Lemma [lem:open-walks-to-common-vertex:exist-open-walk-between-endpoints], and decomposition. ◻

Proof. Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) be the shortest walk between \(i\) and \(j\) that is open given \(C\) such that there is no subwalk including \(\omega\) itself between \(i\) and \(j\) that is open given \(C\setminus \{\, i,j \,\}.\) We consider two cases.

Case 1:  \(C\cap \{\, i,j \,\} = \emptyset.\) In this case, the walk \(\omega\) is open given \(C\setminus \{\, i,j \,\}\). This contradiction the assumption that there is no subwalk open given \(C\setminus \{\, i,j \,\}\) and we have a contradiction.

Case 2:  \(C \cap \{\, i,j \,\} \neq \emptyset.\) Note that the only occurrence of \(i\) on \(\sigma_1\) can be as vertex \(v_1\) and the only occurrence of \(j\) on \(\sigma_m\) can be as vertex \(v_n.\) If the only section containing \(i\) is on \(\sigma_1\) and the only occurrence of \(j\) is on \(\sigma_m\) then \(\omega\) open given \(C\setminus \{\, i,j \,\},\) a contradiction. If \(i\in C\cap \{\, i,j \,\}\) then every occurrence of \(i\) must be in a non-collider section otherwise the walk is not open given \(C\). Similarly for \(j.\) If every occurrence of \(i\) or \(j\) is on collider section that contains a member of \(C\setminus \{\, i,j \,\}\) then \(\omega\) is open given \(C\setminus \{\, i,j \,\},\) a contradiction. Thus there must be a collider section containing a vertex in \(\{\, i,j \,\}\) and no other vertex in \(C\setminus \{\, i,j \,\}\). Without loss of generality, assume \(\sigma_k\) is a collider section containing \(v_l=i\) and no vertex in \(C\setminus \{\, i,j \,\}.\) In this case, the walk \(\omega(v_l,v_n)\) is a shorter walk open given \(C,\) a contradiction.

In all cases we have a contradiction so the lemma must hold. ◻

Proof. Let \(\omega\) be an open walk given \(C\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\). By Lemma 1, we can assume that \(C\cap \{\, i,j \,\}=\emptyset.\) We construct the required walk \(\omega'\) as follows:

If there is a collider section on \(\omega\) that is anterior to \(v_1\) but not anterior to \(C\) then choose \(i\) to be as large as possible such that \(\sigma_i\) is such a collider section and choose \(i=1\) otherwise. If \(i > 1\) then let \(\gamma_i\) be the shortest anterior walk from \(\mathop{\mathrm{first}}(\sigma_i)\) to \(v_1\) and let \(\gamma_1=\left( \right)\) otherwise. Due to the choice of \(\sigma_i\), the walk \(\gamma_i\) contains no vertices in \(C\).

If there is a collider section on \(\omega\) that is anterior to \(v_n\) but not anterior to \(C\) that is not before \(\sigma_i\) then choose \(j\) to be as small as possible but with \(j\geq i\) such that \(\sigma_j\) is such a section and let \(j=m\) otherwise. If \(j\neq m\) then let \(\gamma_j\) be the shortest walk from a vertex \(v_b\) in \(\sigma_j\) to \(v_n\) and let \(\gamma_j=\left( \right)\) otherwise. Again, due to the choice of \(\sigma_j\), the walk \(\gamma_j\) contains no vertices in \(C\).

Finally, let \(\omega'=\gamma_i \mathbin{+}\omega(\mathop{\mathrm{first}}(\sigma_i),\mathop{\mathrm{last}}(\sigma_j)) \mathbin{+}\gamma_j\). The walk \(\omega'\) is an open walk given \(C\) such that all collider sections are anterior to \(C\). ◻

Proof. For the forward direction, assume there is a walk \(\omega\) that is a connecting walk given \(C\). The walk \(\omega\) is also an open walk given \(C\) as every non-collider section contains no vertex in \(C\) and every collider section contains vertex in \(C\) and thus is anterior to \(\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\).

For the backward direction, assume there is a walk between \(i\) and \(j\) that is an open walk given \(C\). From Lemma 1, we can assume that \(C\) does not contain either \(i\) or \(j\). From Lemma [lem:open-give-c:all-colliders-anterior-to-C], we assume that the walk \(\omega\) between \(i\) and \(j\) is open given \(C\) and that every collider section on \(\omega\) is anterior to \(C\). We transform the walk \(\omega\) into walk \(\omega'\) by replacing every collider section \(\tau\) on \(\omega\) that does not contains a vertex in \(C\) with a walk \(\tau'\) between \(\mathop{\mathrm{first}}(\tau)\) and \(\mathop{\mathrm{last}}(\tau)\) that is connecting given \(C\). The walk \(\tau'\) is defined as follows: Let \(\text{\rmfamily\upshape ver}({\tau})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and let \(\gamma_c\) be a shortest anterior walk from a vertex on \(\tau\) to a vertex \(c\in C\). Let the first vertex of \(\gamma'\) be \(v_k\). We define \(\tau'=\tau(v_1,v_k) \mathbin{+}\gamma_c \mathbin{+}\gamma_c(c,v_k) \mathbin{+}\tau(v_k,v_n)\).

Next we show that \(\omega'\) constructed in this way is a connecting walk given \(C\). Consider any collider section \(\tau\) on \(\omega\) that does not contain a vertex in \(C\). Let \(\tau'=\tau(v_1,v_k) \mathbin{+}\gamma_c \mathbin{+}\gamma_c(c,v_k) \\ \mathbin{+}\tau(v_k,v_n)\) with \(\gamma_c\) a shortest anterior walk from \(\tau\) to a vertex \(c\in C\). By choosing the shortest anterior walk the only vertex on \(\gamma'\) in \(C\) is its endpoint \(c\). Thus the only vertex in \(C\) on \(\tau'\) is \(c\) and it appears only once on the walk. If \(\gamma_c\) is a semi-directed walk then \(c\) is on a collider section of \(\gamma_c\mathbin{+}\gamma_c(c,v_k)\) and all other sections of \(\tau'\) are non-collider section on \(\omega'\) due to the fact that the walk \(\tau'\) is strongly out of \(v_1\) and \(v_n\). Furthermore, none of these sections contain a vertex in \(C\). If \(\gamma_c\) is an undirected walk then \(\tau'\) is an undirected walk and every vertex on \(\tau'\) is on a collider section that contains a vertex \(c\in C\).

Thus walk \(\omega'\) constructed in this way is a connecting walk as every collider section contains a vertex in \(C\) and no non-collider section contains a vertex in \(C\). ◻

Proof. Let \(\omega\) is a open walk given \(C\) in graph \(G\) and \(b\) is an internal vertex on a collider section of \(\omega\). It must be the case that \(b\not \in C\) otherwise \(\omega\) would not be an open walk given \(C\). The walks \(\omega(v_1,b)\) and \(\omega(v_n,b)\) are both open given \(C\) as every collider section on these walks is a collider section on \(\omega\) and must contain a vertex in \(\mathop{\mathrm{Ant}}(C,G)\). Furthermore non-collider sections on either of these walk cannot contain a vertex in \(C\) otherwise the walk \(\omega\) would not be open given \(C\). Finally, one of the walks must be strongly out of \(b\) otherwise \(b\) would be on a collider section of \(\omega\). ◻

Proof. Let \(\omega\) be a minimal open walk given \(C\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\). Suppose the lemma is not true. In this case at least one of the endpoints appears on a non-collider section of \(\omega\). Without loss of generality, assume that \(v_1=v_j\) for \(1 < j < n\). Consider the walk \(\omega'=\omega(v_j,v_n)\). The walk \(\omega'\) is an open walk between \(v_1\) and \(v_n\) by Lemma 4. Furthermore, it is strictly shorter than \(\omega\) and only uses vertices on \(\omega\) as it is a subwalk on \(\omega\). Thus \(\omega\) is not a minimal open walk given \(C\) and we have a contradiction. Thus, neither endpoint can appear as an internal vertex on a non-collider section of a minimal open walk. ◻

Proof. Let \(\omega\) be a minimal open walk given \(C\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) such that \(b\) is on a collider section \(\sigma_i\). Let \(f_i=\mathop{\mathrm{first}}(\sigma_i)\).

Proof of (i): Consider the walk \(\omega'=\omega(v_1,f_i)\). The walk \(\omega'\) must be into \(f_i\) due to the fact that \(\sigma_i\) is a collider section. Next we show that \(\omega'\) is open given \(Cv_n \setminus f_i\). Every collider section on \(\omega'\) is a collider section on \(\omega\), and thus, from \(\omega\) being open given \(C\), we have that every collider section on \(\omega'\) is anterior to \(Cv_n\setminus f_i\). Every non-collider section on \(\omega'\) is a non-collider section on \(\omega\) except the last section of \(\omega'\) that consists only of the vertex \(b\). From Lemma 5 and the assumption that \(\omega\) is a minimal open walk, we know that \(v_n\) is not on an internal non-collider section of \(\omega'\). Combining this fact and the fact that \(\omega\) is open given \(C\), it must be the case that no non-collider section \(\omega'\) contains a vertex in \(Cv_n\setminus f_i\). Thus \(\omega'\) is an open walk given \(Cv_n\setminus f_i\).

Proof of (ii): the proof is analogous to the proof of (i). ◻

Proof. Let walk \(\omega\) between \(i\) and \(j\) and walk \(\gamma\) between \(j\) and \(k\) be minimal open walks given \(C\) that are weakly into \(j\). Let \(\omega'=\omega \mathbin{+}\gamma\).

For the forward direction, assume \(\omega \mathbin{+}\gamma\) is open given \(Cj\). Suppose the lemma does not hold and at least one of \(\omega\) and \(\gamma\) are strongly out of \(j\). This implies that \(j\) must be on a non-collider section on \(\omega \mathbin{+}\gamma\) which implies that the walk is not open given \(Cj\) which is a contradiction.

For the backward direction, assume both \(\omega\) and \(\gamma\) are both weakly into \(j\). First from the fact that both walks are open given \(C\), it must be the case that \(j\not\in C\). Furthermore, from Lemma 5, neither \(\omega\) nor \(\gamma\) contain \(j\) on a non-collider section. Next, due to both walks being weakly into \(j\), \(j\) must be on a collider section. All other collider sections are anterial to some vertex in \(C\) and no non-collider section can contain \(C\) or \(j\). Thus the walk is an open walk given \(Cj\). ◻

Proof. Let \(\omega\) be a walk between \(i\) and \(j\) open given \(C\) and \(\gamma\) be a walk between \(j\) and \(k\) given \(C\) and that at least one of \(\omega\) or \(\gamma\) is strongly out of \(j\). Let \(\omega'=\omega \mathbin{+}\gamma\).

Suppose that \(\omega'\) is not open given \(C\).

First, all sections of \(\omega'\) are sections on \(\omega\) or \(\gamma\) except possibly the last section of \(\omega\) and the first section of \(\gamma\). Furthermore every such section is a collider section on \(\omega'\) if and only if it is a collider section on \(\omega\) or \(\gamma\). From the fact that \(\omega\) and \(\gamma\) are open given \(C\), all such sections are open on \(\omega'\) given \(C\). Next the fact that \(\omega\) and \(\gamma\) are open given \(C\) implies that no vertex in the last section of \(\omega\) is in \(C\) and no vertex in the first section of \(\gamma\) is in \(C\). Thus, the only way that \(\omega'\) is not open given \(C\) is if the section containing \(j\) on \(\omega'\) is a collider section. This can only happen if both \(\omega\) and \(\gamma\) are weakly into \(j\) which is a contradiction. Thus the lemma must be true. ◻

Proof. Let \(G\) be a graph.

Property (1): For every vertex \(c\in \mathop{\mathrm{Ant}}(A,G)\) there must be an anterior walk from \(c\) to a vertex in \(A\) which implies the existence of an anterior walk from \(c\) to a vertex in \(A\cup B\) and thus \(c\in \mathop{\mathrm{Ant}}(A\cup C,G)\).

Property (2): Property (1) proves one direction so we just need to show \(ant(A\cup B,G) \subseteq \mathop{\mathrm{Ant}}(A,G)\). For every vertex \(c\in \mathop{\mathrm{Ant}}(A\cup B, G)\) then there is an anterior walk \(\gamma\) from \(c\) to a vertex \(d\) in \(A\cup B\). If \(d\in A\) we are done. Otherwise \(d\in B\). Because \(d\in B\subseteq \mathop{\mathrm{Ant}}(A,G)\) there is a walk \(\gamma'\) from \(d\) to a vertex in \(A\). The walk \(\gamma \mathbin{+}\gamma'\) is an anterior walk from \(b\) to a vertex in \(A\) which proves the claim. ◻

Proof. Let \(G\) be a graph.

Property (1): For every vertex \(c\in \mathop{\mathrm{Post}}(A,G)\) there must be an anterior walk from a vertex in \(A\) to \(c\) which implies the existence of an anterior walk from a vertex in \(A\cup B\) to \(c\) and thus \(c\in \mathop{\mathrm{Post}}(A\cup C,G)\).

Property (2): Property (1) proves one direction of the property so we just need to show \(\mathop{\mathrm{Post}}(A\cup B,G) \subseteq \mathop{\mathrm{Post}}(A,G)\). For every vertex \(c\in \mathop{\mathrm{Post}}(A\cup B)\) then there is an anterior walk \(\gamma\) from a vertex \(d\) in \(A\cup B\) to \(c\). If \(d\in A\) we are done. Otherwise \(d\in B\). Because \(d\in B\subseteq \mathop{\mathrm{Post}}(a,G)\) there is a walk \(\gamma'\) from a vertex in \(A\) to \(d\). The walk \(\gamma \mathbin{+}\gamma'\) is an anterior walk from a vertex in \(A\) to \(d\) which proves the claim. ◻

Proof. Assume \(B\subseteq \mathop{\mathrm{PropAnt}}(A,G)\). \[\begin{array}{lll} B \cup \mathop{\mathrm{PropAnt}}(A\cup B,G) & = B\cup \mathop{\mathrm{Ant}}(A\cup B,G)\setminus (A\cup B) & \text{Definition of \;} \mathop{\mathrm{PropAnt}}. \\ & = \mathop{\mathrm{Ant}}(A\cup B, G)\setminus A & \text{Basic set operations.}\\ & = \mathop{\mathrm{Ant}}(A,G) \setminus A & \text{Lemma~\ref{lem:ant-property}}\\ & = \mathop{\mathrm{PropAnt}}(A,G) & \text{Definition of \;} \mathop{\mathrm{PropAnt}}. \\ \end{array}\] ◻

Proof. Let \(a\in \mathop{\mathrm{Ant}}(b,G)\). This implies there is an edge \({e(a, b)}\) in \(G\) and the walk consisting of this single edge is a walk between \(a\) and \(b\). There is no separating set \(C \subseteq V\setminus \{\, a,b \,\}\) and thus the two vertices are not be separable. ◻

Proof. A self-inducing walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) is an open walk given any vertex set \(C\subseteq V \setminus \{\, v_1,v_n \,\}\) and thus the claim then follows from Lemma 3. ◻

Proof. We prove the claim by induction on the number of vertices.

For the base case we consider treks of length two. In this case there are no internal vertices and the claim holds vacuously.

For the induction case, assume it is true for all treks of length \(n-1\) and show for treks of length \(n\). Let \(\omega=\left( e_1,\ldots,e_n \right)\) be a trek of length \(n\) with vertex sequence \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n+1} \right)\). The subwalk \(\omega'=\left( e_1,\ldots,e_{n-1} \right)\) is a trek of length \(n-1\) and thus, by the induction hypothesis, there is an anterial subwalk from every internal vertex to either \(v_1\) or \(v_n\). If edge \(e_n\) has a tail at \(v_{n}\) then \(v_{n}\) must be anterior to \(v_{n+1}\) and the claim holds. If edge \(e_n\) has an arrowhead at \(v_n\) then no vertex \(v_i\) of \(\omega\) \(i < n\) can be connected to \(v_n\) by a semi-directed walk otherwise \(\omega\) would have a collider section. This implies that either \(v_n\) is connected to \(v_1\) by and undirected walk or there is a semi-directed walk from \(v_n\) to \(v_1\). In either case, the claim holds. As the claim holds whether the last edge has an arrowhead or tail at the last internal vertex the claim holds of any trek of length \(n\). ◻

Proof. Let \(\omega\) be an open walk between \(i\) and \(j\) given \(C\) in a graph \(G\). Every vertex \(b\) on \(\omega\) is on a collider section or a non-collider of \(\omega\).

Case 1:  \(b\) is on a collider section. From the fact that \(\omega\) is open given \(C\), every collider section is anterior to \(C\cup \{\, i,j \,\}\) and thus the every vertex on a collider section must be in \(\mathop{\mathrm{Ant}}(C\cup\{\, i,j \,\},G)\).

Case 2:  \(b\) is on a non-collider section. Every non-collider section is on a maximal trek and, from Lemma 11, every vertex on a maximal trek is anterior to one of its endpoints. Furthermore, every endpoint of a maximal trek on \(\omega\) is either an endpoints of the walk or a vertex on a collider section. Thus every vertex on a maximal trek must be in the set \(\mathop{\mathrm{Ant}}(C\cup\{\, i,j \,\},G)\).

In either case the vertex must be in the set \(\mathop{\mathrm{Ant}}(C\cup\{\, i,j \,\},G)\) which implies the lemma is true. ◻

Proof. For the backward direction, assume that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}}.\) In this case, the vertices \(i\) and \(j\) are separated by \(\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}\) and thus separable.

For the forward direction, we prove the contrapositive. We assume that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {C}\) where \(C=\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}\) and prove that \(i\) and \(j\) are not separable. From, Lemma 3 there must be a walk \(\omega\) between \(i\) and \(j\) that is open given \(C\). We prove by cases.

Case 1:  \(\omega\) contains no collider sections. In this case, all internal vertices are on non-collider sections. If \(\omega\) contains an internal vertex it must be on a non-collider section and in \(C\) which would imply that the walk is not be open given \(C\), so \(\omega\) has no internal vertices. Thus \(\omega\) must contain a single edge \({e(i, j)}\) which, by Lemma 9, implies that \(i\) and \(j\) are not separable.

Case 2:  \(\omega\) contains a collider sections. From the fact that \(\omega\) is open given \(C\), every collider section must be anterior to \(C\cup \{\, i,j \,\}.\) Thus, if \(\omega\) had an internal vertex on a non-collider section, this vertex, by Lemma 12, would be in \(C\) and the walk would be closed given \(C.\) This implies that every internal vertex on \(\omega\) is on a collider section. These facts imply that \(\omega\) is a self-inducing walk which, by Lemma 10, implies that \(i\) and \(j\) cannot be separated.

The lemma holds in each of the exhaustive cases and thus the lemma holds. ◻

Proof. Let graph \(G\) contain a non-trivial walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) such that \(\omega\) is not a self-inducing walk.

The maximal walk decomposition of \(\omega\) must contain a non-trivial maximal trek because \(\omega\) is not a self-inducing walk. Let \(\omega(v_i,v_k)\) with \(i < k\) be a non-trivial maximal trek. Note that there must be an internal vertex \(v_j\) with \(i < j < k\) on this maximal trek and this vertex is on a non-collider section of \(\omega.\) We consider three cases.

Case 1:  Neither \(v_i\) nor \(v_k\) are on collider section of \(\omega.\) In this case \(i=1\) and \(k=n\) and \(\omega\) is a trek. From the fact that \(\omega\) is non-trivial it contains an internal vertex on a non-collider section. This vertex must be in \(C\) and thus the walk is not open given \(C.\)

Case 2:  Either \(v_i\) or \(v_k\) are on collider sections of \(\omega\) but not both. Without loss of generality, assume \(v_k\) is on a collider section and thus \(i=1.\) If \(v_k\not \in C\) then there is a collider section on \(\omega\) that is not anterior to \(C\) and thus the walk is not open given \(C.\) On the other hand, if \(v_j\in C\) then the internal vertex \(v_j\) is in \(C\). This implies that there is a non-collider section of \(\omega\) that contains a vertex in \(C\) and the walk is not open given \(C.\)

Case 3:  Both \(v_i\) and \(v_k\) are on collider sections of \(\omega.\) If either \(v_k\not \in C\) or \(v_i\not\in C\) there is a collider section on \(\omega\) that is not anterior to \(C\) and thus the walk is not open given \(C.\) On the other hand, if \(\{\, v_i,v_k \,\} \subseteq C\) then the internal vertex \(v_j\) is in \(C\). This implies that there is a non-collider section of \(\omega\) that contains a vertex in \(C\) and the walk is not open given \(C.\) ◻

Proof. This follows from Lemmas 9, 10, and 13. ◻

Proof. Let \(G\) be a graph. For the forward direction, assume that \(G\) is separable. Aiming for a contradiction, suppose that \(G\) contains a self-inducing walk between \(i\) and \(j\). This implies \(i\not\in \mathop{\mathrm{Adj}}(j,G)\) and, from Lemma 10, that \(i\) and \(j\) are not separable. Thus we have a contradiction. Thus \(G\) must not contain a self-inducing walk.

For the reverse direction, assume that \(G\) contains no self-inducing walk. Aiming for a contradiction, assume that \(G\) is not separable. This implies that there is a pair of vertices \(i\not\in \mathop{\mathrm{Adj}}(j,G)\) such that \(i\) and \(j\) are not separable. This implies that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}}\) which implies that there is a walk \(\omega\) between \(i\) and \(j\) that is open given \(\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}.\) From Lemma 14 and \(i\not\in \mathop{\mathrm{Adj}}(j,G)\), however, this walk \(\omega\) must be a self-inducing walk. This is a contradiction as \(G\) does not contain any self-inducing walks and the lemma must hold. ◻

Proof. Let \(\omega\) be an inducing walk in graph \(G\) with vertex sequence \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and let \({e(v_i, v_j)}\) for \(j > i+1\) be a chord of the inducing walk.

Assume \(\omega\) is minimal but that the chord does not satisfy condition (i) or (ii). We consider the possible endpoint for \({e(v_i, v_j)}\). First note that there can be no edge between the endpoints \(v_1\) and \(v_n\) as in this case \(\omega\) would not be an inducing walk. If \(v_i\) and \(v_j\) are both two internal vertices of \(\omega\) then we are in case (i). If there is either an undirected edge or a bidirected edge, however, then the walk \(\omega(v_1,v_i)\mathbin{+}\left( {e(v_i, v_j)} \right) \mathbin{+}\omega(v_j,v_n)\) would be an inducing walk that uses a subset of the vertices in \(\omega\) and thus \(\omega\) is not minimal. This is a contradiction and thus there is no chord violating condition (i). If one of \(v_i\) and \(v_j\) is an endpoint and the other is internal then we are in case (ii). If \(v_i=v_1\) and there is an arrowhead at \(v_j\) on chord \({e(v_i, v_j)}\) then \(\left( {e(v_1=v_i, v_j)} \right) \mathbin{+}\omega(v_j,v_n)\) would be an inducing walk that uses a subset of the vertices in \(\omega\) and thus \(\omega\) is not minimal. If \(v_j=v_n\) and there is an arrowhead at \(v_i\) on chord \({e(v_i, v_j)}\) then \(\omega(v_1,v_i)\mathbin{+}\left( {e(v_i, v_n=v_j)} \right)\) would be an inducing walk that uses a subset of the vertices in \(\omega\). In either case, \(\omega\) is not minimal. This is a contradiction and there is no chord violating condition (ii).

For the other direction, assume \(\omega\) is an inducing walk such that all of its chords satisfy conditions (i) and (ii). Assume that there is an inducing walk \(\omega'\) between \(v_1\) and \(v_n\) that uses a subset of vertices in \(\omega\). In this case, there must be a chord of \(\omega\) that is on \(\omega'\). Let \({e(v_i, v_j)}\) with \(i < j\) be the first chord, an edge on \(\omega'\) not on \(\omega\). If the first edge of \(\omega'\) is a chord it must be \(v_1=v_i\) and \(v_j \neq v_n\) as such a chord does not satisfy either (i) or (ii). In this case, the edge has a tail at \(v_j\) and cannot be on a collider section on \(\omega'\). This implies that \(\omega'\) is not an inducing walk. If the edge is not the first edge then the vertex \(v_i\) must be an internal vertex on \(\omega'\). If \(v_j=v_n\) then there must be a tail at \(v_i\) on the edge and \(v_i\) is not on a collider section of \(\omega'\). Again \(\omega'\) is not an inducing walk. Finally, if both \(v_i\) and \(v_j\) are internal vertices on \(\omega'\) then the chord must be directed and thus both \(v_i\) and \(v_j\) cannot be a collider section of \(\omega'\) and thus it is not an inducing walk. In each of these cases, we have a contradiction as \(\omega'\) is assumped to be an inducing walkand thus no such \(\omega'\) exists and \(\omega\) must be a minimal inducing walk. ◻

Proof. Let \(\omega\) be a minimal inducing walk with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) in graph \(G\). First we prove (i). Assume \(\mathop{\mathrm{first}}(\sigma_i,G) \not\in \mathop{\mathrm{Adj}}(v_1,G)\). This implies that \(\omega'= \omega(v_1,\mathop{\mathrm{first}}(\sigma_i,G))\) is an inducing walk. The walk \(\omega'\) is a minimal inducing walk, by Lemma 15 and the fact that \(\omega\) is a minimal inducing walk. The proof for (ii) is symmetric to the proof of (i). ◻

Proof. Let \(G\) be a graph containing a minimal inducing walk\(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) that discriminates section \(\sigma_i\). Assume the lemma does not hold. Then there must be a chord \({e(v_i, v_j)}\) such \(i=1\) or \(i=n-1\) and \(v_j\) is on \(\sigma_i\). Without loss of generalityassume \(i = 1\).

Case 1:  \({e(v_i, v_j)}\) has an arrowhead at \(v_j\). In this case, the walk \(\left( {e(v_i, v_j)} \right)\mathbin{+}\omega(v_j,v_n)\) is an inducing walk that uses a subset of the vertices on \(\omega\) and thus \(\omega\) is not a minimal inducing walk. This is a contradiction.

Case 2:  \({e(v_i, v_j)}\) has a tail at \(v_j\). In this case, the section is not discriminated by \(\omega\) which is a contradiction.

In either case we have a contradiction and the lemma must hold. ◻

Proof. Let \(\omega\) be a minimal inducing walk in graph \(G\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) that discriminates two collider sections \(\sigma_i\) and \(\sigma_j\) with \(1 < i < j < n\). Let \(\omega_1 = \omega(v_1, \mathop{\mathrm{first}}(\sigma_j))\) and \(\omega_n = \omega(\mathop{\mathrm{last}}(\sigma_i), v_n)\). Both \(\omega_1\) and \(\omega_n\) are collider walks. From Lemma 17 both are inducing walks. Finally, by Lemma 15 and the fact that \(\omega\) is a minimal inducing walk, both are minimal inducing walks. ◻

Proof. If \(\omega\) is a minimal inducing walkthat is not a self-inducing walkthen it must have a discriminated section. The correctness of the walk decomposition function follows from the fact that each added walk is a discriminating inducing walkand Lemma 18, which allows us to decompose a walk into minimal inducing walks with fewer discriminated sections. The walk decomposition function $ {_{iw}}$ is invertible due to the fact that no internal section on a minimal inducing walkcan be repeated. ◻

Proof. We prove by induction on the number of collider section on the inducing walk. Let \(\omega\) be a minimal inducing walkthat is not a self-inducing walkin a graph \(G\). It must have a discriminated section \(\sigma\).

For the base case, \(\sigma\) is the only collider section of \(\omega\). In this case, the collider section \(\sigma\) must be discriminated by \(\omega\) and we are done.

For the induction case, we assume it is true for walks with \(n\) collider sections and show for \(n+1\) collider sections. First, the collider section \(\sigma\) is discriminated by \(\omega\). If there is a collider section \(\sigma'\) on \(\omega\) closer to \(v_1\) than \(\sigma\) then the walk \(\omega(v_1, \mathop{\mathrm{first}}(\sigma))\) is a collider walk. By Lemma 17 and the fact that \(\omega\) is a minimal inducing walk, the subwalk is also a minimal inducing walk. The walk has at most \(n\) collider sections and thus, by the induction hypothesis, the walk discriminates \(\sigma'\). If there is a collider section \(\sigma'\) on \(\omega\) closer to \(v_n\) than \(\sigma\) then the walk \(\omega(\mathop{\mathrm{last}}(\sigma), v_n)\) is a collider walk. By Lemma 17 and the fact that \(\omega\) is a minimal inducing walk, the subwalk is a minimal inducing walk. The walk has at most \(n\) collider sections and thus, by the induction hypothesis, the walk discriminate \(\sigma'\).

Thus, every collider section of \(\omega\) is discriminated by some discriminating inducing walkthat is a subwalk of \(\omega\). ◻

Proof. Let walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) be a discriminating inducing walkin graph \(G\) that discriminates \(\sigma_i\). Every collider section other than \(\sigma_i\) is anterior to \(v_1\) or \(v_n\). Suppose the lemma does not hold and \(\sigma_i\) is anterior to \(\sigma_j\). In this case \(\sigma_i\) is anterior to \(v_1\) or \(v_n\) and thus \(\sigma_i\) is not discriminated by \(\omega\). This is a contradiction so the lemma must hold. ◻

Proof. Let \(G\) be a separable graph. Assume the lemma is not true and that \(\omega\) is a minimal inducing walkthat contains a section \(\sigma_i\) anterior to an adjacent section. From Lemma 20, there is a discriminating inducing walk\(\omega'\) that discriminates \(\sigma\). Result then follows from Lemma 21. ◻

Proof. Let \(G\) be a separable graph and \(\omega\) be a minimal inducing walk with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) with a chord between vertex \(v_i\) on section \(\sigma_a\) and vertex \(v_j\) on \(\sigma_{a+1}\).

Case 1:  \(1 < a < m - 1\). In this case, the chord is between two internal sections. By Lemma 15 and minimality, the chord must be directed. Without loss of generality, assume \(v_i \ \text{---}\!\!\!\!\succ\! \ v_j\). This, however, contradicts Lemma 22.

Case 2:  \(a=1 \vee a = m - 1\). In this case, the chord is between an internal section and its adjacent terminal section. By Lemma 15 and minimality, the chord must have a tail at the internal vertex. This, however, contradicts Lemma 22.

In either case we have a contradiction and the lemma must hold. ◻

Proof. Suppose the lemma is not true. Let \(G\) be a separable graph contain a walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) such that there is a chord on collider section \(\sigma_a=\left( {v}_{i},\ldots,{v}_{l} \right)\). Let chord \({e(v_{j}, v_{k})}\) on \(\sigma_a\) be the chord that maximizes \(|k-j|\) and \(i \leq j < k \leq l\).

Case 1:  \({e(v_{j}, v_{k})}\) is undirected or bidirected. In this case the walk \(\omega(v_1,v_j)\mathbin{+}\left( {e(v_j, v_k)} \right) \mathbin{+}\\ \omega(v_k,v_n)\) is an inducing walk that uses a subset of the vertices in \(\omega\) and thus \(\omega\) is not a minimal inducing walk. This is a contradiction.

Case 2:  \({e(v_{j}, v_{k})}\) is directed. Without loss of generality assume that \({e(v_{j}, v_{k})}\) has an arrowhead at \(v_k\). In this case, the walk \(\left( {e(v_j, v_k)} \right)\mathbin{+}\omega(v_k, \mathop{\mathrm{first}}(\sigma_{a+1}))\) is a collider trisection. Furthermore, by Lemma 23 the walk is unshielded and thus is a minimal inducing walk. Due to the fact that \(\sigma_a\) is an undirected walk, the collider trisection is also a self-inducing walk which, by Theorem 10, contradicts the assumption that \(G\) is a separable graph.

Both cases lead to contradictions so the lemma must hold. ◻

Proof. Assume the lemma is not true and let \(G\) be a separable graph containing a minimal inducing walkwith a chord between internal sections that are part of a semi-directed circuit in \(G\). Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) be a shortest minimal inducing walkin \(G\) with a chord between internal sections that are part of a semi-directed circuit in \(G\). The chord must be directed otherwise \(\omega\) would not be a minimal inducing walk. Let chord \({e(v_i, v_j)}\) of \(\omega\) be the chord between internal sections and on a semi-directed circuit with the largest jump, that is, such that \(|j-i|\) is as large as possible. Without loss of generality, assume that \(i<j\) and that edge \({e(v_i, v_j)}\) has an arrowhead at \(v_j\). Let \(v_i\) be on \(\sigma_s\) and \(v_j\) be on \(\sigma_u\). It must be the case that \(1 < s < u < m\). Let \(l_i = \mathop{\mathrm{last}}(\sigma_i)\) and \(f_i=\mathop{\mathrm{first}}(\sigma_i)\). In order for \(v_1\) and \(v_n\) to be separable there must be a discriminated section \(\sigma_t\) on \(\omega\) otherwise \(\omega\) is a self-inducing walk.

Case 1:  Section \(\sigma_t\) is not after \(\sigma_s\) on \(\omega\), that is, \(1< t \leq s\). We consider two subcases. First, \(l_t\not\in \mathop{\mathrm{Adj}}(v_n,G)\). In this case, then the walk \(\omega(l_t, v_n)\) is a minimal inducing walkcontaining a chord between internal sections that is on a semi-directed circuit that is shorter than \(\omega\). This is a contradiction. Second, \(l_t\in \mathop{\mathrm{Adj}}(v_n,G)\). In this case, by Lemma 15, the edge \({e(l_t, v_n)}\) must have a tail which implies that \(\sigma_t\) is not discriminated. Again we have a contradiction.

Case 2:  Section \(\sigma_t\) is not before \(\sigma_u\) on \(\omega\), that is, \(u \leq t < m\). We again consider two subcases. First, \(f_t\not\in \mathop{\mathrm{Adj}}(v_1,G)\). In this case, the walk \(\omega(v_1, f_t)\) is a minimal inducing walkcontaining a chord between internal sections that is on a semi-directed circuit that is shorter than \(\omega\). This is a contradiction. Second, \(f_t\in \mathop{\mathrm{Adj}}(v_1,G)\). In this case, by Lemma 15, the edge \({e(f_t, v_1)}\) must have a tail at \(f_t\) which implies \(\sigma_t\) is not a discriminated section. Again we have a contradiction.

Case 3:  Section \(\sigma_t\) is between \(\sigma_s\) and \(\sigma_u\) on \(\omega\). If there are multiple discriminated section between \(\sigma_s\) and \(\sigma_u\) then choose \(\sigma_t\) to be the closest to \(\sigma_u\). We again consider two subcases. First, \(l_t \in \mathop{\mathrm{Adj}}(v_n,G)\). In this case, the edge \({e(l_t, v_n)}\) must have a tail at \(l_t\) by Lemma 15 which implies \(\sigma_t\) is not a discriminated section. This is a contradiction. Second, \(l_t \not\in \mathop{\mathrm{Adj}}(v_n,G))\). In this case, the walk \(\omega(l_t,v_n)\) must be a self-inducing walk as every collider section between \(\sigma_t\) and \(\sigma_n\) is not discriminated. This, by Theorem 10, contradicts the assumption that \(G\) is separable.

In each case we have a contradiction. Thus, a minimal inducing walk in a separable graph can have no chord between internal sections that is part of a semi-directed circuit. ◻

Proof. Suppose the lemma is not true. Let \(G\) be a separable graph that contains \(\omega\) minimal inducing walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) such that not all of the internal endmarks on \(\omega\) are exclusive. Without loss of generality assume that the edge is \({e(v_{i-1}, v_{i})}\) for \(1 < i \leq n\) and the edge does not have an exclusive endpoint at \(v_i\).

Case 1:  \(i=2\). In this case, the there must be an \({e'(v_1, v_2)}\) with an tail at \(v_2\). This implies that \(\sigma_2 \subseteq \mathop{\mathrm{Ant}}(\sigma_1,G)\) which contradicts Lemma 22.

Case 2:  \(i > 2\) and \({e(v_{i-1}, v_{i})}\) is bidirected. In this case, the there must be an \({e'(v_{i-1}, v_i)}\) with a tail at \(v_i\). Because the edge is bidirected, the two endpoints are on adjacent sections of \(\omega\). These sections are both collider sections on \(\omega\). Thus there is an internal section anterial to an adjacent section which contradicts Lemma 22.

Case 3:  \(i > 2\) and \({e(v_{i-1}, v_{i})}\) is undirected. In this case, the there must be an \({e'(v_{i-1}, v_i)}\) with an arrowhead at \(v_i\). Because the edge is undirected, the two endpoints are on the same section \(\sigma_a\) of \(\omega\). This implies that the walk \(\left( {e'(v_{i-1}, v_i)} \right)\mathbin{+}\omega(v_i,\mathop{\mathrm{first}}(\sigma_{a+1}))\) is a collider trisection. Furthermore, by Lemma 23, the trisection is unshielded an thus minimal inducing walk. This implies, however, that the trisection is a self-inducing walk which contradicts Theorem 10.

In all three cases we have a contradiction and thus the lemma must hold. ◻

Proof. Let \(\omega\) be a shortest open walk between \(a\) and \(b\) given conditioning set \(C\) and the walk decomposition of \(\omega\) be \(\left( \tau_1,\gamma_1,\tau_2,\ldots, \gamma_{n-1},\tau_n \right)\) with maximal treks \(\tau_i\) open given \(C\) and maximal collider walks \(\gamma_i\) open given \(C\).

Assume that the lemma is not true. Let maximal treks \(\tau_k\) with \(\text{\rmfamily\upshape ver}({\tau_k})=\left( a_1,\ldots, a_m \right)\) and \(\tau_l\) with \(\text{\rmfamily\upshape ver}({\tau_l})=\left( b_1,\ldots, b_n \right)\) be such that there is a chord \({e(a_i, b_j)}\). Let walk \(\omega'=\omega(a_1,a_i) \mathbin{+}{e(a_i, b_j)} \mathbin{+}\omega(b_j,j)\) be the walk obtained by replacing the subwalk from \(a_i\) to \(b_j\) in \(\omega\) by the chord \({e(a_i, b_j)}\). We show that for any chord between \(a_i\) and \(b_j\) the walk \(\omega'\) is a shorter open walk than \(\omega\) which is a contradiction.

If the edge \({e(a_i, b_j)}\) is undirected then there is a section \(\sigma\) on \(\omega'\) that contains both \(a_i\) and \(b_j\). Furthermore, \(\sigma\) must be a non-collider on \(\omega'\) given \(C\) and cannot contain a member of \(C\) as all vertices on \(\sigma\) are on non-collider sections of \(\omega\). In this case, \(\omega'\) is a shorter open walk than \(\omega\) which is a contradiction.

If the edge \({e(a_i, b_j)}\) is directed, we assume, without loss of generality that it is oriented \(a_i \ \text{---}\!\!\!\!\succ\! \ b_j\). In this, case the section \(\sigma\) of \(\omega'\) containing \(a_i\) must be an open non-collider section given \(C\). The section \(\sigma'\) of \(\omega'\) containing \(b_j\) need not be a non-collider section. In the case that it is a non-collider section it is open given \(C\) and \(\omega'\) is a shorter open walk than \(\omega\) which is a contradiction. Next we consider the case in which \(\sigma'\) is a collider section on \(\omega'\). In this case, the section containing \(b_j\) on \(\omega\) is a non-collider section which, by Lemma 12, implies that there is an anterior walk \(\gamma=\left( a_1=b_j,\ldots, a_n \right)\) from \(b_j\) to some vertex \(a_n\in C \cup \{\, i,j \,\}\). In this case, \(\omega'\) must be a shorter open walk than \(\omega\), which is a contradiction.

If the edge \({e(a_i, b_j)}\) is bidirected, \(a_i\) and \(b_j\) are in separate sections on \(\omega'\). As in the case above, if the sections are non-colliders they must be open and if they are colliders, they must be anterior to \(C\cup\{\, i,j \,\}\). Thus, in any combination, \(\omega'\) is a shorter open walk than \(\omega\), which is a contradiction.

Hence, there can be no chord between vertices of non-collider sections on distinct maximal treks. ◻

Proof. Let \(\gamma\) be a maximal collider walk on a shortest open walk \(\omega\). Let \(\tau\) and \(\tau'\) be the adjacent maximal treks adjacent to \(\gamma\) on \(\omega\). The endpoints \(\gamma\) are both on non-collider section of distinct maximal treks of \(\omega\). From Lemma 27, there can be no chord between the endpoints and thus \(\gamma\) must be an inducing walk. Furthermore, the walk \(\gamma\) must be minimal or there would be a shorter open walk than \(\omega\). ◻

Proof. Suppose the lemma is not true. Let \(G\) be a graph that contains a walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) that is open given \(C\) such that there are vertices \(v_i\) on non-collider section \(\sigma_h\) and \(v_k\) on non-collider section \(\sigma_j\) on \(\omega\) such that \(v_i = v_k\). Without loss of generalityassume \(i < k\) which implies \(h \leq j\). The walk \(\omega(v_1,v_i) \mathbin{+}\omega(v_j,v_n)\) is a shorter open walk given \(C\) and thus we have a contradiction and the lemma must be true. ◻

Proof. Let \(G\) be a graph and let \(H=\text{\rmfamily\upshape Anterialize}(G)\). If there is no edge between \(a\) and \(b\) in \(G\) then there is no edge between \(a\) and \(b\) in \(H\). If there are one or more edges between \(i\) and \(j\) in \(G\) then only one edge is added to \(H\) because the choice of edge endmarks is uniquely determined by the existence of anterior walks between \(i\) and \(j\) in \(G\). ◻

Proof. For the forward direction, suppose \(G\) is an anterial graph. Assume that the anterial endmark property does not hold. In this case there is an edge \({e(a, b)}\) with an arrowhead at \(b\) and there is an anterior walk \(\omega\) from \(b\) to \(a\). We consider two cases. First, \({e(a, b)}\) has an arrowhead at \(a\). In this case, \(a \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ b\) and \(b \in \mathop{\mathrm{Ant}}(a,G)\) which imply that \(G\) is not anterial. Second, \({e(a, b)}\) has a tail at \(a\). In this case, the walk \(\omega \mathbin{+}\left( {e(a, b)} \right)\) is a semi-directed circuit and again \(G\) is not anterial. In either case we have a contradiction so the forward direction holds.

For the backward direction, let \(G\) be a simple graph and assume that the graph satisfies the anterial endmark property but is not anterial. We consider two cases. First there is an edge \(a \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ b\) and an anterior walk \(\omega\) from \(b\) to \(a\) in \(G\). In this case, the graph \(G\) does not satisfy the anterial endmark property. Second there is an edge \(a \ \text{---}\!\!\!\!\succ\! \ b\) and an anterior walk \(\omega\) from \(b\) to \(a\) in \(G\). In this case, the graph \(G\) does not satisfy the anterial endmark property. In either case we have a contradiction and the backward direction holds. ◻

Proof. From Lemma 30, the graph \(\text{\rmfamily\upshape Anterialize}(G)\) is simple. Graph \(\text{\rmfamily\upshape Anterialize}(G)\) satisfies the anterial endmark property because every edge \({e(a, b)}\) added to the the graph \(\text{\rmfamily\upshape Anterialize}(G)\) has a tail at \(a\) if and only if there is an anterior walk from \(a\) to \(b\). Thus, by Lemma 31, the graph \(\text{\rmfamily\upshape Anterialize}(G)\) is an anterial graph. ◻

Proof. Let \(G\) be a graph and let \(H=\text{\rmfamily\upshape Anterialize}(G)\). The algorithm results in a graph \(\text{\rmfamily\upshape Anterialize}(G)\) with the same adjacencies as the input graph \(G\) due to the fact that for every edge \({e(a, b)}\) in \(G\) some edge \({e'(a, b)}\) is added to \(H\) and if there is no edge \({e(a, b)}\) in \(G\) then no edge is added between \(a\) and \(b\) in \(H\). ◻

Proof. Let \(G\) be a graph containing an \({e(a, b)}\) with a tail at \(a\). In this case \(a\in \mathop{\mathrm{Ant}}(b,G)\). This implies that the \({e'(a, b)}\) in \(\text{\rmfamily\upshape Anterialize}(G)\) must be either \(a \ \text{---}\ b\) or \(a \ \text{---}\!\!\!\!\succ\! \ b\). ◻

Proof. For the first direction, let \(\gamma\) be an anterior walk from \(v_1\) to \(v_n\) in \(G\). From Lemma 33, we know that there is a walk \(\omega\) in \(\text{\rmfamily\upshape Anterialize}(G)\) with the same vertex sequence. Furthermore, from Lemma 34 the walk \(\omega\) must also be an anterior walk as every undirected edge in \(G\) remains an undirected edge in \(\text{\rmfamily\upshape Anterialize}(G)\) and every directed edge in \(G\) is either an undirected or directed edge in \(\text{\rmfamily\upshape Anterialize}(G)\).

For the other direction, let \(\omega\) be an anterior walk in \(\text{\rmfamily\upshape Anterialize}(G)\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\). Associate with each edge \({e(v_i, v_{i+1})}\) on \(\omega\) an anterior walk on \(\gamma_i\); one must exist due to the fact that an edge \({e(v_i, v_j)}\) in \(\text{\rmfamily\upshape Anterialize}(G)\) has a tail at \(v_i\) if and only if there is an anterior walk from \(v_i\) to \(v_j\) in \(G\). The walk \(\gamma=\gamma_1 \mathbin{+}\cdots \mathbin{+}\gamma_{n-1}\) is an anterior walk from \(v_1\) to \(v_n\) in \(G\). ◻

Proof. Let graph \(G\) contains a minimal inducing walk\(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and let \(G'=\text{\rmfamily\upshape Anterialize}(G)\).

From Lemma 33 there is a walk \(\omega'\) in \(G'\) such that \(\text{\rmfamily\upshape ver}({\omega'})=\left( {v}_{1},\ldots,{v}_{n} \right)\). We consider the possible edge types for each edge \({e(v_{i}, v_{i + 1})}\) for \(1 \leq i < n\) on \(\omega\) and the corresponding type of edge in \(\omega'\).

Case 1:  \(v_i \ \text{---}\ v_{i+1}\). In this case, the edge must be an internal edge (i.e.,\(1 < i < n-1\)) and the corresponding edge on \(\omega'\) must be undirected as \(v_i\in \mathop{\mathrm{Ant}}(v_j,G)\) and \(v_j\in \mathop{\mathrm{Ant}}(v_i,G)\).

Case 2:  \(v_i \ \text{---}\!\!\!\!\succ\! \ v_j\). In this case, the edge must be a terminal edge of \(\omega\) and \(i=1\) or \(i=n\). By Lemma 22, the arrowhead at \(v_j\) must be an arrowhead in the corresponding edge on \(\omega'\).

Case 3:  \(v_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_j\). In this case, either \(v_i\) or \(v_j\) must be an internal vertex on \(\omega\). If either endpoint is an internal vertex on \(\omega\), by Lemma 22, it must have an arrowhead endmark at the vertex in the corresponding edge on \(\omega'\).

In all cases, all internal endmarks of edges on \(\omega\) are preserved on edges in \(\omega'\) and thus \(\omega \equiv \omega'\). ◻

Proof. Let graph \(G\) contains a minimal inducing walk\(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and let \(G'=\text{\rmfamily\upshape Anterialize}(G)\). From Lemma 36 there is a walk \(\omega'\equiv \omega\) in \(G'.\) Due to the fact that \(\omega\) is an inducing walk and Lemma 33, \(\omega'\) must be an inducing walk. Next we show that inducing walk \(\omega'\) is a minimal inducing walk. Suppose that \(\omega'\) is not a minimal inducing walk. In this case, there must be a minimal inducing walk\(\gamma'\) that uses a subset of the vertices of \(\omega'\). Let \({e'(v_i, v_j)}\) be the first edge on \(\gamma'\) that is a chord on \(\omega'\).

Case 1:  \({e'(v_i, v_j)}\) is the first edge of \(\gamma'\).

In this case, \(i = 1\) and the edge \({e'(v_i, v_j)}\) has an arrowhead at \(v_j\) and there must be an edge \({e(v_1, v_j)}\) in \(G\) with an arrowhead at \(v_j\). But this implies that \(\left( {e(v_1, v_j)} \right) \mathbin{+}\omega(v_j,v_n)\) is a shorter inducing walkusing a subset of the vertices on \(\omega\). This implies that \(\omega\) is not a minimal inducing walkwhich is a contradiction.

Case 2:  \({e'(v_i, v_j)}\) is the last edge of \(\gamma'\). In this case \(j=n\) and the proof follows as in Case 1.

Case 3:  \({e'(v_i, v_j)}\) is an internal edge of \(\gamma'\). In this case \(v_i\) and \(v_j\) must both be on collider sections of \(\omega'\). From the fact that the edge is on a minimal inducing walkit must either be bidirected or undirected.

Case 3.1:  \(v_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_j\). In this case, there must be an edge \(v_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_j\) in \(G\). This, however, implies that \(\omega(v_1,v_i)\mathbin{+}\left( v_j \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_j \right) \mathbin{+}\omega(v_j,v_n)\) is a shorter inducing walk using a subset of vertices on \(\omega\). This implies that \(\omega\) is not a minimal inducing walkwhich is a contradiction.

Case 3.2:  \(v_i \ \text{---}\ v_j\). In this case, there must either be an chord \(v_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_j\) or a chord with a directed edge between \(v_i\) and \(v_j\) in \(G\). As in Case 3.1, a bidirected edge leads to a contradiction. If, however, there is a directed edge in \(G\), from Lemma 25, we obtain a contradiction.

Thus in all cases we have a contradiction and the lemma must hold. ◻

Proof. Let \(G\) be a separable graph and let \(G' = \text{\rmfamily\upshape Anterialize}(G)\) contain a minimal inducing walk\(\omega'\) with \(\text{\rmfamily\upshape ver}({\omega'})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega'})=\left( {\sigma'}_{1}, \ldots, {\sigma'}_{m} \right)\).

From Lemma 33 there is a walk \(\omega\) in \(G\) such that \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\). Suppose the lemma is not true and that \(\omega \not \equiv \omega'\). Because \(\text{\rmfamily\upshape Anterialize}\) only removes arrowheads there is some \(\sigma_k'\) with \(1 < k < m\) on \(\omega'\) that contains an edge \(v_{l} \ \text{---}\ v_{l + 1}\) such that the edge \({e(v_l, v_{l+1})}\) on \(\omega\) either has an arrowhead at \(v_l\) or \(v_{l+1}\). Without loss of generality assume that \({e(v_l, v_{l+1})}\) has an arrowhead at \(v_l\). Choose \(\sigma_j'\) to be the collider section on \(\omega'\) closest to \(\sigma_1\) that contains an edge \(v_{i} \ \text{---}\ v_{i + 1}\) and an edge \({e(v_i, v_{i+1})}\) with an arrowhead at \(v_i\) on \(\omega\).

Case 1:  \(\omega(v_1,v_{i+1})\) is a collider walk.

By Lemma 32, \(G'\) is an anterial graph. This implies that there can be no chord \({e'(v_{i+1}, v_h)}\) for \(v_h\) on section \(\sigma_{j-1}'\) of \(\omega'\) as the chord must be directed due to the fact that \(\omega'\) is a minimal inducing walkand this would imply there is a bidirected edge with anterial endpoints. This implies, by Lemma 33 and the fact that does not add arrowheads, that \(\omega(l_{j-1},v_{i+1})\) with \(l_{j-1}=\mathop{\mathrm{last}}(\sigma_j)\) is a minimal inducing walkin \(G\). By Lemma 37, this would imply that \({e'(v_{i}, v_{i+1})}\) on \(\omega'\) has an arrowhead at \(v_i\) which is a contradiction.

Case 2:  \(\omega(v_1,v_{i+1})\) is a not a collider walk.

In this case, there must be an edge \(v_{l} \ \text{---}\ v_{l + 1}\) on \(\omega'(v_1,v_{i+1})\) such that the edge \({e(v_l, v_{l+1})}\) has an arrowhead at \(v_{l+1}\) on \(\omega\). Choose \(\sigma_f'\) to be the collider section on \(\omega'\) closest to and before \(\sigma_j'\) that contains an edge \(v_{h} \ \text{---}\ v_{h + 1}\) and an edge \({e(v_h, v_{h+1})}\) with an arrowhead at \(v_h\) on \(\omega\).

Again by Lemma 32, there can be no chord \({e'(v_{h}, v_l)}\) for \(v_l\) on \(\sigma_{f+1}'\) as the chord must be directed due to the fact that \(\omega'\) is a minimal inducing walkand this would imply the existence of a bidirected edge with anterial endpoints. This implies, by Lemma 33 and the fact that does not add arrowheads, that \(\omega(l_{j-1},v_{i+1})\) with \(l_{j-1}=\mathop{\mathrm{last}}(\sigma_j)\) is a minimal inducing walkin \(G\). By Lemma 37, this would imply that \({e'(v_{h}, v_{h+1})}\) on \(\omega'\) has an arrowhead at \(v_{h+1}\) which is a contradiction.

In both cases we have a contradiction and thus \(\omega \equiv \omega'\). ◻

Proof. Let \(G\) be a graph and \(G' = \text{\rmfamily\upshape Anterialize}(G)\).

First, by Lemma 32, the graph \(G'\) is anterial.

Next we show that if \(G\) is a separable graph then \(G \equiv G'\). To prove equivalence, from the definition of equivalence and Lemma 3, we show that \(G\) and \(\text{\rmfamily\upshape Anterialize}(G)\) have the same open walks. For the forward direction, let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) be a shortest open walk given \(C\) in \(G\). From Lemma 28, every maximal collider walk on \(\omega\) is a minimal inducing walk. From Lemma 36, there is a walk \(\omega'\) in \(G'\) such that \(\omega \equiv \omega'\). From Lemma 35, \(\omega'\) must be an open walk given \(C\) in \(G'\). For the backward direction, let \(\omega'\) with \(\text{\rmfamily\upshape ver}({\omega'})=\left( {v}_{1},\ldots,{v}_{n} \right)\) be a shortest open walk given \(C\) in \(G'\). From Lemma 28, every maximal collider walk on \(\omega'\) is a minimal inducing walk. From Lemma 38, there is a walk \(\omega'\) in \(G'\) such that \(\omega \equiv \omega'\). From Lemma 35, \(\omega'\) must be an open walk given \(C\) in \(G'\). Combining the forward and backward directions we have shown that \(G\equiv G'\).

Finally, if \(G\) is a separable graph then the graph \(G'\) must be separable as it is equivalent to separable graph and has the same adjacencies. ◻

Proof. The result is a consequence of Theorem 3 and Corollary 2 of [13]. ◻

Proof. For the forward direction, assume \(G\) be an essentially separable graph. By definition, there is an equivalent separable graph \(G_{sep}\). From Theorem 12 there is an equivalent separable anterial graph \(G_{ant}\). As \(G_{ant}\) is an acylic graph, thus the forward direction is proved.

For the backward direction, assume \(G\) is essentially acyclic. Thus there is an acyclic equivalent graph \(G_{acyc}\equiv G\). From Lemma 39, there is an equivalent separable acyclic graph \(G_{sep}\equiv G_{acyc}\). Thus the backward direction is proved. ◻

Proof. The lemma holds due to the fact that equivalent graphs define equivalent independence models (Proposition 6) and the set of distributions defined by a graphical model is defined in terms of the independence modelof the defining graph and the fixed defining family of distributions. ◻

Proof. By definition, \({\cal G}_{sep}\equiv \mathcal{E}({\cal G}_{sep})\). \({\cal G}_{ant}^{sep}= {\cal G}_{ant}\cap {\cal G}_{sep}\) and thus \({\cal G}_{ant}^{sep}\subseteq {\cal G}_{sep}\) which implies that \({\cal G}_{ant}^{sep}\sqsubseteq {\cal G}_{sep}\). From Theorem 12, we have that \({\cal G}_{sep}\sqsubseteq {\cal G}_{ant}^{sep}\). Combining these facts we have \({\cal G}_{sep}\equiv {\cal G}_{ant}^{sep}\). By transitivity, we have \(\mathcal{E}({\cal G}_{sep})\equiv {\cal G}_{ant}^{sep}\), and, by Lemma 40, \({\cal M}_{\mathcal{E}({\cal G}_{sep})}\equiv {\cal M}_{{\cal G}_{ant}^{sep}}\). ◻

Proof. From Lemma 39 we have \({\cal G}_{acyc}\sqsubseteq {\cal G}_{ant}^{sep}\). From the fact that \({\cal G}_{ant}^{sep}\subseteq {\cal G}_{acyc}\) we also have \({\cal G}_{ant}^{sep}\sqsubseteq {\cal G}_{acyc}\). This implies that \({\cal G}_{acyc}\equiv {\cal G}_{ant}^{sep}\). Using this fact and Corollary 2, we have \(\mathcal{E}({\cal G}_{sep})\equiv {\cal G}_{acyc}\). Then, by Lemma 40, it also follows that \({\cal M}_{\mathcal{E}({\cal G}_{sep})}\equiv {\cal M}_{{\cal G}_{ant}^{sep}}\). ◻

Proof. Suppose that the induced independence property does not hold in some semi-graphoid independence model.

Let independence model\(I=\left( V,T \right)\) be such a semi-graphoid and let \(A,B,C,D\) be disjoint subsets of \(V\) such that the induced independence property does not hold. In that case, it must be the case that (1) \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {C}\) and (2) \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {B}\ |\ {CD}\). In order for the property to not hold it must be the case that either \({A} \perp\!\!\!\!\perp_{I} {D}\ |\ {CB}\) or \({D} \perp\!\!\!\!\perp_{I} {B}\ |\ {CA}\). We consider these two cases.

Case 1:  (3) \({A} \perp\!\!\!\!\perp_{I} {D}\ |\ {CB}\). From (1) and (3) and contraction we have (4) \({A} \perp\!\!\!\!\perp_{I} {BD}\ |\ {C}\). From (4) and weak union we get (5) \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {CD}\) which contradicts (2).

Case 2:  (6) \({D} \perp\!\!\!\!\perp_{I} {B}\ |\ {CA}\). From (1) and (6), symmetry and contraction we have (7) \({B} \perp\!\!\!\!\perp_{I} {AD}\ |\ {C}\). From (7) and weak union and symmetry we get (8) \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {CD}\) which contradicts (2).

In either case we have a contradiction so the induced independence property must hold in every semi-graphoid independence model. ◻

Proof. Let \(G\) be a graph. From Propositions 4 and 5, \({I}{(G)}\) is a graphoid that satisfies weak-transitivity. The result then follow from Theorem 35. ◻

Proof. Let independence model \(I\) be graphical. This implies there is a graph \(G\) such that \(I={I}{(G)}\). From Propositions 4 and 5, \({I}{(G)}\) is a composition graphoid that satisfies weak-transitivity.

For the forward direction, assume that \(I\) satisfies pairwise upward stability. Aiming for a contradiction, assume that \(I\) contains an inducing vertex \(k\) for \(\left( A,B,C \right)\). Thus we have \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {C}\) and \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {B}\ |\ {Ck}\). From \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {B}\ |\ {Ck}\) and composition there is some \(a\in A\) and \(b\in B\) such that \({a} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {b}\ |\ {Ck}\). From \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {C}\) and decomposition we have \({a} \perp\!\!\!\!\perp_{I} {b}\ |\ {C}\). Thus, \(I\) does not satisfy pairwise upward stability. This is a contradiction and this direction must hold.

For the reverse direction, assume that \(I\) contains no inducing vertex. Aiming for a contradiction, assume \(I\) does not satisfy pairwise upward stability. In this case there are vertices \(i,j\) and sets \(C\subset D\) such that \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {C}\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {j}\ |\ {D}\). If \(|D\setminus C|>1\), we can choose sets \(C' \supseteq C\) and \(D'\subseteq D\) such that \(|D' \setminus C'| < |D\setminus C|\), \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {C}\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {j}\ |\ {D}\). Thus, without loss of generality, we assume \(|D\setminus C|=1\). Let \(k=D\setminus C\). In this case \(k\) is an inducing vertex for \(\left( i,j,C \right)\). This is a contradiction and this direction must hold. ◻

Proof. Let \(G\) be a graph. For the forward direction, assume \(G\) is essentially undirected. By Lemma 41, \({I}{(G)}\) satisfies pairwise upward stability. In addition, \({I}{(G)}\) is graphical, thus by Lemma 42, we have that \({I}{(G)}\) has no inducing vertices.

For the backward direction, assume that \({I}{(G)}\) contains no inducing vertices. By Lemma 42, we have that \({I}{(G)}\) satisfies pairwise upward stability. By Lemma 41 we have that \(I(G)\) must be equivalent to some undirected graph and thus \(G\) is essentially undirected. ◻

Proof. Let \(G\) be a graph such \(b\in \operatorname{IV}(i,j,C,G)\). From \(b\in \operatorname{IV}(i,j,C,G)\) we have that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb}\). From Proposition 13 we have \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {b}\ |\ {Cj}\) and \({j} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {b}\ |\ {Ci}\). This implies that the there are walks \(\omega_i\) between \(i\) and \(b\) that is open given \(Cj\) and \(\omega_j\) between \(j\) and \(b\) that is open given \(Ci\). The walk \(\omega_i(i,b) \mathbin{+}\omega_j(b,j)\) is a walk between \(i\) and \(j\) and is open given \(Cb\) if and only if both \(\omega_i\) and \(\omega_j\) are into \(b\). Suppose that there is a walk \(\omega_i'\) between \(i\) and \(b\) open given \(Cj\) that is not weakly into \(b\). In this case, the walk \(\omega_i' \mathbin{+}\omega_j\) is a walk open given \(C\) which is a contradiction. Similarly, suppose there is a walk \(\omega_j'\) between \(j\) and \(b\) open given \(Ci\) that is not weakly into \(b\). In this case, the walk \(\omega_i \mathbin{+}\omega_j'\) is a walk open given \(C\) which is a contradiction. Thus every such walk must be weakly into \(b\). ◻

Proof. Suppose the proposition is false and that, \(b\in \operatorname{IV}(i,j,C,G)\) and \(b\in \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\). From the definition of an inducing vertex and \(b\in \operatorname{IV}(i,j,C,G)\) we know that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb}\). From \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb}\), there is a walk \(\omega\) between \(i\) and \(j\) that is a connecting walk given \(Cb\). This implies that \(b\not\in \{\, i,j \,\}\) otherwise the walks \(\omega\) would be closed. Thus we have \(b\in \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}\). From \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\), \(\omega\) is not a connecting walk given \(C\). The fact that \(\omega\) is open given \(Cb\), implies that \(\omega\) contains no non-collider section with a vertex in \(Cb\). Thus \(\omega\) must contain one or more collider sections closed given \(C\) but open given \(Cb\). Thus, from \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb}\), each such closed collider sections must contain \(b\). Because \(b\in \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}\) there must be an anterior walk from \(b\) to a vertex in \(C\cup\{\, i,j \,\}\) in \(G\). Thus, \(\omega\) is an open walk given \(C\) which, by Lemma 3 implies there is a connecting walk given \(C\) which is a contradiction. Therefore, the proposition must be true. ◻

Proof. Let \(G\) be a graph such that, \({A} \perp\!\!\!\!\perp_{G} {B}\ |\ {C}\), \(D \subseteq V_{\mathrel{\gtrapprox}ABC} = \mathop{\mathrm{Ant}}(ABC,G) \setminus ABC\). We prove by induction on the size of \(D\)

For the base case, \(|D|=0\) we have \(C=CD\) and thus the independence \({A} \perp\!\!\!\!\perp_{G} {B}\ |\ {CD}\) holds by assumption.

For this induction case we assume that the property holds for all sets \(D'\subset D\) (i.e., \(|D'|\leq n-1\)) and and show that it holds for \(|D|=n\). Choose a vertex \(k\in D\) and let \(E=CD\setminus \{\, k \,\}.\) By the induction hypothesis we have \({A} \perp\!\!\!\!\perp_{G} {B}\ |\ {E}.\) Aiming at a contradiction assume that \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {B}\ |\ {Ek}.\) This implies that there is some \(i\in A\) and \(b\in B\) such that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Ek}.\) From \({A} \perp\!\!\!\!\perp_{G} {B}\ |\ {E}\) we have that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {E}.\) Thus we have that \(k\in \operatorname{IV}(i,j,E,G)\). From Proposition 44, \(k\not \in \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\) and, thus, \(k\in \mathop{\mathrm{Ant}}(E\setminus\{\, i,j \,\},G).\) From \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Ek}\), there is some connecting walk between \(i\) and \(j\) given \(Ck\) in \(G\). Let \(\omega\) be any such connecting walk. It must be the case that \(k\) in not on any non-collider section of \(\omega\) and every collider section on \(\omega\) contains a vertex in \(Ek\) otherwise \(\omega\) would not be a connecting walk. Next, from \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {E}\), there must be on some collider section in \(\omega\) that does not contain any vertex in \(E\) but contains \(k\). This, however, implies that \(\omega\) is open given \(E\) as every such collider section is anterior to \(E\) because \(k\in \mathop{\mathrm{Ant}}(E\setminus\{\, i,j \,\},G).\) From Lemma 3, this implies there is a connecting walk between \(i\) and \(j\) given \(E\) which contradicts \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {E}.\) Thus, we have a contradiction and the lemma must be true. ◻

Proof. Follows from Lemma 45. ◻

Proof. Follows from Lemma 45. ◻

Proof. Aiming for a contradiction, assume that the claim does not hold for graph \(G\).

Choose \(D\) to be a smallest set such that there exists \(A,B,C\) such that \({A} \perp\!\!\!\!\perp_{G} {B}\ |\ {CD}\), \(D\cap V_{\mathrel{\gtrapprox}ABC} = D\cap \mathop{\mathrm{Ant}}(ABC,G) =\emptyset\) and \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {B}\ |\ {C}\). Due to the fact that \(D\cap \mathop{\mathrm{Ant}}(ABC,G) =\emptyset\), there exists a subset \(E \subseteq D\) such that \(E \cap \mathop{\mathrm{Ant}}(CD\setminus E,G) =\emptyset\). From the fact, \(D\) is chosen to be a smallest set and \(D \cap \mathop{\mathrm{Ant}}(ABC,G) = \emptyset\), it must be the case that \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {B}\ |\ {CD\setminus E}\). This implies that there is a connecting walk between \(i\in A\) and \(j\in B\) given \(CD\setminus E\) in \(G\). Let \(\omega\) be any such connecting walk. Because \(\omega\) is a connecting walk given \(CD\setminus E\), every collider section of \(\omega\) must contain a member of \(CD\setminus E\). From the choice of \(E \cap \mathop{\mathrm{Ant}}(CD\setminus E,G) =\emptyset\), no collider section containing a vertex in \(E\) can contain a vertex in \(CD\setminus E.\) This implies that \(\omega\) must also be a connecting walk given \(CD\). This is a contradiction so the proposition holds. ◻

Proof. We assume that \(a \mathrel{\approx_G}b\) in graph \(G\). In this case, there is an anterior walk \(\omega_{ab}\) from \(a\) to \(b\) in \(G\) and an anterior walk \(\omega_{ba}\) from \(b\) to \(a\) in \(G\). For the first direction, let \(c\in \mathop{\mathrm{Ant}}(a,G)\). This implies that there is an walk \(\omega_{ca}\) from \(c\) to \(a\) in \(G\). The walk \(\omega_{ca} \mathbin{+}\omega_{ab}\) is an anterior walk from \(c\) to \(b\) which implies that \(c\in \mathop{\mathrm{Ant}}(b,G)\). The other directions follows by a similar argument. ◻

Proof. Let graph \(G\) be such that \(a\in \operatorname{IV}(i,j,C)\) and \(b\in [a]_\approx^G\). This implies that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Ca}\). Thus there is an open walk \(\omega\) between \(i\) and \(j\) given \(Ca\) which implies \(\omega\) contains no non-collider section that contains a vertex in \(Ca\). Because, \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\), there are no non-collider section that is anterior to \(a\) but not \(C\). From Lemma 47, such a section is anterior to \(b\) for any \(b\in [a]_\approx\). This implies that the walk is open given \(Cb\) and thus the claim holds. ◻

Proof. Let \(G=\left( V,E \right)\) be acyclic, that is, it contains no semi-directed circuit, and let \(a =_G b\).

Case 1:  \(a = b\). In this case, the equality gives \(a \sim_G b\).

Case 2:  \(a \neq b.\) In this case, we have \(a \not\in \mathop{\mathrm{Ant}}(b,G) \wedge b \not\in \mathop{\mathrm{Ant}}(a,G)\). From that fact that \(a\neq b\) there must be anterior walks from \(a\) to \(b\) and from \(b\) to \(a\). Let \(\gamma_{ab}\) be an arbitrary anterior walk from \(a\) to \(b\) and let \(\gamma_{ba}\) be an arbitrary anterior walk from \(b\) to \(a\). If either or both of these walks is not undirected then the walk \(\gamma_{ab} \mathbin{+}\gamma_{ba}\) would be a semi-directed circuit and \(G\) would not be acyclic. This implies that all anterior walk between \(a\) and \(b\) are undirected and thus \(a \sim_G b.\) In either case we have \(a \sim_G b\) so the lemma holds. ◻

Proof. Let \(G\) be an acyclic graph. Assume that the inducing set property does not hold. In that case there is a set \(D\) such that \(d\in D\) and \(D=[d]_\approx^G\) and \(D \in \operatorname{IS}(A,B,C,G)\) and for \(E\), a non-empty subset \(E\subseteq [d]_\approx^G\) we have \({A} \perp\!\!\!\!\perp_{G} {B}\ |\ {CE}\). From \(D \in \operatorname{IS}(A,B,C,G)\), we have \({A} \perp\!\!\!\!\perp_{I} {B}\ |\ {C}\) and \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {B}\ |\ {CD}\). From \({A} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {B}\ |\ {CD}\) there must be a walk \(\omega\) between \(i\in A\) and \(j\in B\) that is connecting given \(CD\). From Lemma 12, every vertex on \(\omega\) is in \(\mathop{\mathrm{Ant}}(CDij,G)\). This implies that no vertex in \(D\) can be a non-collider on \(\omega\) otherwise the walk \(\omega\) would not be a connecting walk given \(CD\). Note that for every non-empty \(E\subset [d]_\approx^G\) it is the case that \(\mathop{\mathrm{Ant}}(CDij,G)=\mathop{\mathrm{Ant}}(CDij,G)\). This fact implies that \(\omega\) is also open given \(CE\) which is a contradiction. Thus the claim holds. ◻

Proof. Let \(\mathrel{\lessapprox}\) be a preorder for \(V\) such that independence model\(I\) for \(V\) satisfies ordered upward separation stability, ordered downward separation stability, and the inducing set equivalence property with respect to \(\mathrel{\lessapprox}\). First, if \(I\) satisfies ordered upward separation stability it satisfies OUS.

Next, we show that \(I\) must satisfy ODS. Aiming for a contradiction, assume that \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {C}\) and \(k\) be a vertex such that \(k \in V \setminus V_{>C\setminus k}\) and \(k\in V \setminus V_{\mathrel{\gtrapprox}ij}\) but that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {j}\ |\ {C\setminus k}.\)

Let \(E= C\cap [k]_\approx\) and \(D = C\setminus E.\) From ordered downward separation stability (Lemma 46), we have that \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {D}.\)

We continue by cases.

Case 1:  \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {Dk}\). We consider two sub-cases.

Case 1.1: , \(|E|=1\). In this case, \(C=Dk\), and from the fact that \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {D}\), we have \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {C\setminus k}\) which is a contradiction.

Case 1.2:  \(|E|>1\). In this case, we again have \(C=DE\). From the fact that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {j}\ |\ {C\setminus k}\) and \({i} \perp\!\!\!\!\perp_{I} {j}\ |\ {D}\), we have \(E\setminus k \in \operatorname{IS}(i,j,D,I)\). Thus we have that \(E\in \operatorname{IS}(i,j,D,I)\) and, by the inducing set equivalence property, we have \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {j}\ |\ {C}\) which is a contradiction.

Case 2:  \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{}\ {j}\ |\ {Dk}\). In this case, \(k\in \operatorname{IS}(i,j,D,G)\). From the inducing set equivalence property we have that \(E\in \operatorname{IS}(i,j,D,I)\) and it follows that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{I}\ {j}\ |\ {C}\). Again we have a contradiction.

In every case we have a contradiction and thus ODS must hold in \(I\). ◻

Proof. For forward direction, we assume \(G\) is essentially separable. By Theorem 11, \(G\) is essentially acyclic which implies that there is an equivalent acyclic graph \(H \equiv G\). By Proposition 49, \({I}{(G)}={I}{(H)}\) satisfies the inducing set equivalence property with respect to \(\mathrel{\lessapprox}_G\).

For the other direction, we assume there is a graph \(G\) such that \({I}{(G)}\) satisfies the inducing set equivalence property with respect to preorder \(\mathrel{\lessapprox}_G\). From Propositions 4 and 5, \({I}{(G)}\) is a compositional graphoid that satisfies weak-transitivity. From Lemmas 45 and 46, \({I}{(G)}\) satisfies ordered upward separation stability and ordered downward separation stability with respect to \(\mathrel{\lessapprox}_G\). From Lemma 50, \({I}{(G)}\) satisfies ODS and OUS with respect to \(\mathrel{\lessapprox}_G\). Thus we can apply Theorem 36 to obtain the conclusion that \(I\) is acyclic. From the definitions of an acyclic independence model and essentially acyclic and Theorem 11, we have that \(G\) is essentially separable. ◻

Proof. Let \(G\) and \(H\) be two equivalent separable graphs. The properties of vertex separability and induced arrowheads are separational properties and invariant to separation equivalence. That is, these properties are completely determined by the independence and dependence statements true in the graph. As \(G\) and \(H\) are equivalent they must agree on these properties. ◻

Proof. Let \(G\) and \(H\) be two separable graph. From the fact that the two graphs are separable, vertex separability corresponds to adjacency. Thus the two graphs have the same adjacency. ◻

Proof. Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) be a minimal discriminating inducing walkthat discriminates section \(\sigma_k\) in a graph \(G\), and \(d\) is on \(\sigma_i \neq \sigma_j\). Suppose that there is a \(C\subseteq V\) such that \(d\in \operatorname{IV}(v_1,v_n,C,G)\). Then by Proposition 44, \(d\not\in \mathop{\mathrm{Ant}}(\{\, v_1,v_n \,\},G)\). This cannot be the case as all sections other than \(\sigma_k\) must be anterior to the endpoints of \(\omega\). Thus we have a contradiction and for all \(C\) it is the case that \(d \not\in \operatorname{IV}(v_1,v_n,C,G)\). ◻

Proof. Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) be a minimal discriminating inducing walkthat discriminates section \(\sigma\) in a separable graph \(G\) and \(b\in \mathop{\mathrm{Post}}(\sigma,G)\). From separability of \(G\) we have that \({v_1} \perp\!\!\!\!\perp_{G} {v_n}\ |\ {C}\) for \(C=\mathop{\mathrm{PropAnt}}(\{\, v_1,v_n \,\},G)\). The walk \(\omega\) is open given \(b\) and thus, by Lemma 3, \({v_1} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {v_n}\ |\ {Cb}\). Thus \(b \in \operatorname{IV}(v_1,v_n,C,G)\). ◻

Proof. Follows from Lemmas 53 and 54. ◻

Proof. Let \(G\) be a graph containing an edge \({e(d, b)}\) that is an induced arrowhead at \(b\). In this case, there are vertices \(v_1\) and \(v_n\) vertex set \(C\) such that \(b\in \operatorname{IV}(v_1,v_n,C,G)\) and \(d\not\in \operatorname{IV}(v_1,v_n,C,G)\).

From \(b\in \operatorname{IV}(v_1,v_n,C,G)\) and Lemma 43 there is a vertex set \(C\) and connecting walks \(\gamma_1\) between \(v_1\) and \(b\) open given \(Cv_n\) and \(\gamma_n\) between \(v_n\) and \(b\) open given \(Cv_1\) both weakly into \(b\) such that \({v_1} \perp\!\!\!\!\perp_{G} {v_n}\ |\ {C}\).

Suppose that \({e(d, b)}\) does not have an exclusive arrowhead at \(b\) in \(G\). Let \({e'(d, b)}\) be an edge with a tail at \(b\) in \(G\). Consider the walk \(\omega'=\gamma_1(v_1,b) \mathbin{+}\left( {e'(d, b)}, {e'(d, b)} \right) \mathbin{+}\gamma_n(b,v_n)\). The walk \(\omega'\) is open given \(Cd\). This however implies that \(d\in \operatorname{IV}(i,j,C,G)\) and we have a contradiction. Thus the edge \({e(d, b)}\) must have an exclusive arrowhead at \(b\) in \(G\). ◻

Proof. Let \(G\) and \(G'\) be anterial graphs with the same adjacencies and same induced arrowheads.

We prove that every minimal inducing walkin \(G\) is a minimal inducing walkin \(G'\) by induction on the number of collider sections.

For the base case, we consider a minimal inducing walk\(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and collider section \(\sigma=\left( v_2,v_{n-1} \right)\) in \(G\). By Lemma 55, the edge \({e(v_1, v_2)}\) on \(\omega\) has an induced arrowheadat \(v_2\) and the edge \({e(v_{n-1}, v_n)}\) on \(\omega\) has an induced arrowheadat \(v_{n-1}\). This implies the edge \({e'(v_1, v_2)}\) on \(\omega'\) has an induced arrowheadat \(v_2\) and the edge \({e'(v_{n-1}, v_n)}\) on \(\omega'\) has an induced arrowheadat \(v_{n-1}\) in \(G'\). By Proposition 23, these edges have arrowheads at \(v_2\) and \(v_{n-1}\).

By Lemma 24, \(\sigma\) is chordless in \(\omega\) and must also be chordless in \(\omega'\) due to \(G\) and \(G'\) having the same adjacencies.

Suppose \(\sigma\) is not a collider section on \(\omega'\) in \(G'\). In this case there must be an edge \({e'(v_{i}, v_{i + 1})}\) with \(1 < i < n-1\) with an arrowhead at either \(v_i\) or \(v_{i+1}\). Without loss of generalityassume there is an arrowhead at \(v_i\). Furthermore choose smallest \(j > 1\) such that there is an edge \({e'(v_{j}, v_{j + 1})}\) with an arrowhead at \(v_j\). In this case the walk \(\omega'(v_1,v_{j+1})\) is an unshielded collider trisection due to Lemma 23 and the fact that \(G\) and \(G'\) have the same adjacencies. This implies that \({e'(v_{j}, v_{j + 1})}\) has an induced arrowhead at \(v_j\) which in turn implies that \({e(v_{j}, v_{j + 1})}\) on \(\omega\) has an induced arrowhead. Finally, by Proposition 23, the arrowhead must be exclusive in \(G\) and \(\sigma\) is not a collider section which is a contradiction.

For the inductive case, we assume that the lemma is true for minimal inducing walks with \(n\) collider sections and prove for \(n+1\) collider section. Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) be a minimal inducing walkwith \(n+1\) collider section. \(\omega\) must discriminate some section \(\sigma_j\) otherwise it would be a self-inducing walkand that would imply that \(G\) is not separable by Theorem 10.

Let \(\gamma'\) with \(\text{\rmfamily\upshape ver}({\gamma'})=\left( {v}_{i},\ldots,{v}_{k+1} \right)\) be the collider trisection containing \(\sigma_j\) on \(\omega'\). In that case, by an argument similar to the base case, the edge \({e'(v_{i}, v_{i + 1})}\) and the edge \({e'(v_{k}, v_{k + 1})}\) have arrowheads at their internal vertices and \(\gamma(v_{i+1},v_{k})\) is a collider section.

If \(i > 2\) then by Lemmas 16 and 17, \(\omega(v_1,v_{i+1})\) must be a minimal inducing walkand there must be must be a minimal inducing walk\(\omega'(v_1,v_{i+1})\).

Similarly, if \(k < n-1\) then by Lemmas 16 and 17, \(\omega(v_k, v_n)\) must be a minimal inducing walkand there must be a minimal inducing walk\(\omega'(v_k, v_n)\).

Thus, \(\omega'(v_1,v_n)\) is an inducing walk. If \(\omega'(v_1,v_n)\) is not a minimal inducing walkthen there must be an edge \({e((, v)}_h,v_j)\) with \(h < i\) and \(v_j\) on \(\sigma_j\) with an arrowhead at \(v_j\) or \({e((, l)},v_j)\) with \(l > k\) and \(v_j\) with an arrowhead at \(v_j\). In either case, \(\omega(v_1,v_n)\) cannot be a minimal inducing walkwhich is a contradiction. Thus \(\omega'(v_1,v_n)\) is a minimal inducing walk. ◻

Proof. Let \(G\) and \(G'\) be two anterial graphs with the same adjacencies and same minimal inducing walks. Let walk \(\omega\) be a shortest open walk given \(C\) in \(G\) and let \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape decomp}_w(\omega)=\left( \tau_1, \gamma_1, \tau_2,\ldots, \gamma_{m-1},\tau_m \right)\). From \(G\) and \(G'\) having the same adjacencies, there is a walk \(\omega'\) in \(G'\) with \(\text{\rmfamily\upshape ver}({\omega'})=\left( {v}_{1},\ldots,{v}_{n} \right)\). Suppose that \(\omega \not \equiv \omega'\). In order for this to be the case, the walk decompositions of the two walks must be different. First note that if two walks have different maximal treks they must have different maximal collider walks. Thus there must be a \(\gamma_i\) on \(\omega\) such that \(\gamma_i'\) on \(\omega'\) is not a maximal collider walk on \(G'\). From Lemma 28, every \(\gamma_i\) on \(\omega\) must be a minimal inducing walkin \(G\). Anterial graphs are simple graphs and thus every endmark on an edge is exclusive, thus \(\gamma_i \equiv \gamma_i'\). Suppose, however, that \(\gamma_i'\) is not a maximal collider walk. In this case there must be a subwalk \(\omega'(v_h,v_j)\) that contains \(\gamma_i'\) that is a maximal collider walkon \(\omega'\). This must be an inducing walkdue to Lemma 27 and the fact that \(G\) and \(G'\) have the same adjacencies. In this case, there must be a minimal inducing walk\(\gamma'\) between \(v_h\) and \(v_j\) that contains a subset of the vertices on \(\omega'(v_h,v_j)\) in \(G'\). Thus there must be a minimal inducing walk\(\gamma \equiv \gamma'\) in \(G\). This however contradicts the assumption that \(\omega\) is a shortest open walk as the walk \(\omega(v_1,v_h)\mathbin{+}\gamma \mathbin{+}\omega(v_j,v_n)\) would be a shorter open walk given \(C\). Thus there is no such \(\gamma_i\) and \(\omega\equiv \omega'\). ◻

Proof. Let \(\omega\) be a discriminating inducing walk between \(i\) and \(j\) that discriminates section \(\sigma\) in graph \(G\). Because \(i\) and \(j\) are separable there is some set that separates them. Let \(C\) be an arbitrary separating set for \(i\) and \(j\), that is, \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\). Let \(v\) be a arbitrary vertex in \(\mathop{\mathrm{Post}}(\sigma,G)\). The walk \(\omega\) is open given \(C\cup\{\, v \,\}\) and, by Lemma 3 there is a connecting walk \(\omega'\) in \(G\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cv}\). Thus \(v\) is an inducing vertex for \(i\) and \(j\) given \(C\). ◻

Proof. Let \(G\) be an anterial graph and \(\omega\) be a shortest anterior walk with vertex sequence \(\text{\rmfamily\upshape ver}({\omega})=\left( v_1,\ldots,v_n \right)\).

Suppose that there \(\omega\) has a chord \({e(v_i, v_j)}\) for \(i < j-1\). If the edge has a tail at \(b_i\) then there would be a shorter anterior walk \(\gamma(v_1,v_i)\mathbin{+}{e(v_i, v_j)}\mathbin{+}\gamma(v_j,v_m)\) an thus there must be an arrowhead at \(v_i\). However, if \(v_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_j\) then there would be a bidirected edge with one endpoint having anterior walk to the other which contradicts \(G\) being an anterial graph. Finally, if \(v_i \ \!\prec\!\!\!\!\text{---}\ v_j\) then there would be a semi-directed circuit in \(G\) which again contradicts \(G\) being an anterial graph. Thus, a shortest anterior walk must be chordless in an anterial graph. ◻

Proof. Let \(G\) be an anterial graph. Assume the lemma is not true and that \(\omega\) with \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) is a minimal inducing walkthat contains a section anterior to an adjacent section. Without loss of generalityassume that \(\sigma_i\) is anterior to \(\sigma_{i+1}\) and that there is an anterior walk \(\gamma'=\text{\rmfamily\upshape ver}({\gamma'})=\left( {v}_{p},\ldots,{v}_{q} \right)\) with \(v_p\) on \(\sigma_i\) and \(v_q\) on \(\sigma_j\). Let \(l_i=\mathop{\mathrm{last}}(\sigma_i)\) and \(f_{i+1}=\mathop{\mathrm{first}}(\sigma_{i+1})\) and \(\gamma= \omega(l_i, v_p) \mathbin{+}\gamma' \mathbin{+}\omega(v_q, f_{i+1})\). The edge \({e(l_i, f_{i+1})}\) on \(\omega\) must either be \(l_i \ \text{---}\!\!\!\!\succ\! \ f_{i+1}\) or \(l_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ f_{i+1}\). In the first case, the circuit \(\gamma \mathbin{+}\left( {e(l_i, f_{i+1})} \right)\) is a semi-directed circuit and \(G\) is not an anterial graph. This is a contradiction. In the second case, \(l_i \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ f_{i+1}\) has an anterior walk from one endpoint to the other and thus \(G\) is not an anterial graph. This is a contradiction. In either case, we have a contradiction and thus the lemma must be true. ◻

Proof. Let \(G\) and \(G'\) be separable anterial graphs with the same adjacencies and same minimal inducing walks.

Aiming for a contradiction, assume that \(G\not\equiv G'\). Let there be a walk between \(v_1\) and \(v_n\) that is connecting given \(C\) in one walk but not the other. Without loss of generality, assume \({v_1} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {v_n}\ |\ {C}\) and \({v_1} \perp\!\!\!\!\perp_{G'} {v_n}\ |\ {C}\).

Choose \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape decomp}_w(\omega)=\left( \tau_1, \gamma_1, \tau_2,\ldots, \gamma_{m-1},\tau_m \right)\) to be a shortest open walk given \(C\) in \(G\) and let \(\omega'\) be a walk in \(G'\) with \(\text{\rmfamily\upshape ver}({\omega'})=\left( {v}_{1},\ldots,{v}_{n} \right)\). \(\omega'\) must not be open given \(C\) in \(G'\) due to \({v_1} \perp\!\!\!\!\perp_{G'} {v_n}\ |\ {C}\).

From Lemma 57, we have \(\omega \equiv \omega'\) which implies that \(\text{\rmfamily\upshape sec}({\omega})=\text{\rmfamily\upshape sec}({\omega'})\). Let \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{p} \right)\), \(f_i=\mathop{\mathrm{first}}(\sigma_i)\) and \(l_i = \mathop{\mathrm{last}}(\sigma_i)\). Note that \(\text{\rmfamily\upshape sec}({\omega})=\text{\rmfamily\upshape sec}({\omega'})\) due to the fact that \(\omega \equiv \omega'\).

Choose smallest \(j\) with \(1 < j < p\) such that \(\omega'(v_1,f_{j+1})\) is not open given \(C\). There must be one otherwise \(\omega'(v_1,v_l)\) would be an open walk given \(C\).

Let \(\gamma_d=\omega(l_h,f_{j+1})\) be a minimal discriminating inducing walkthat discriminates \(\sigma_j\) on walk \(\omega(v_1,f_{j+1})\). Note that \(1 \leq h < j\). It must be the case that \(\sigma_j\) is anterior to \(Cv_1\) in \(G\) otherwise the walk \(\omega\) would not be open in \(G\). Furthermore, \(\sigma_j\) is not anterior to \(C\cup\{\, v_1,f_{j+1} \,\}\) in \(G'\) otherwise the walk \(\omega'(v_1,f_{j+1})\) would be open given \(C\).

Let \(\gamma_f= \text{\rmfamily\upshape ver}({\gamma'})=\left( {a}_{1},\ldots,{a}_{q} \right)\) be a shortest anterior walk from \(f_j\) to a vertex in \(C\cup \{\, v_1,f_{j+1} \,\}\) in \(G\) and let \(\gamma_f'\) be the corresponding walk in \(G'\). By Lemma 59, \(\gamma_f\) must be chordless and, thus, by \(G\) and \(G'\) having the same adjacencies, \(\gamma_f'\) is also chordless.

Choose \(r\) to be largest such that \(a_r\in \mathop{\mathrm{Post}}(\sigma_j,G')\) and let \(s=r+1\) and thus \(a_s \not \in \mathop{\mathrm{Post}}(\sigma_j,G')\). Note that \({e'(a_r, a_s)}\) on \(\gamma_f'\) must have an arrowhead at \(a_r\).

Suppose \(a_s \not \in \mathop{\mathrm{Adj}}(l_{j-1},G')\). In this case the walk \(\omega'(l_{j-1},f_j) \mathbin{+}\gamma'_f(f_j,a_r) \mathbin{+}\left( {e'(a_r, a_s)} \right)\) in \(G'\) must contain a unshielded collider trisection not in \(G\) which is a contradiction due to the fact that the two graphs have the same minimal inducing walks. Thus \(a_s \in \mathop{\mathrm{Adj}}(l_{j-1},G')\).

Suppose that \(a_s \not \in \mathop{\mathrm{Adj}}(f_{j+1},G')\) and let \(\gamma_l\) be a shortest anterior walk from \(l_j\) to \(a_r\) in \(G'\). By Lemma 59, \(\gamma'_l\) is chordless. In this case, the walk \(\omega'(f_{j+1},l_j) \mathbin{+}\gamma'_l(l_j,a_r) \mathbin{+}\left( {e'(a_r, a_s)} \right)\) in \(G'\) must contain an unshielded collider trisection not in \(G\) which is a contradiction. Thus \(a_s \in \mathop{\mathrm{Adj}}(f_{j+1},G')\).

Suppose that \(a_r \neq f_j\). In this case, The walk \(\gamma_f'(f_j,a_s)\) must be semi-directed since otherwise \(\sigma_j\) would be anterior to \(\sigma_{j-1}\). This implies that the walk \(\gamma_f'(f_j,a_s)\) must contain an unshielded collider trisection not in \(G\). This is a contradiction. Thus \(a_r = f_j\).

Both \({e(l_{j-1}, a_s)}\) and \({e(f_{j+1}, a_s)}\) must be into \(a_s\) by Lemma 58 due to the fact that \(l_{j-1}\) and \(f_{j+1}\) are on sections of discriminating inducing walk\(\gamma_d\) that discriminates \(\sigma_j\).

This implies that both \({e'(l_{j-1}, a_s)}\) and \({e'(f_{j+1}, a_s)}\) must be into \(a_s\) as \(G\) and \(G'\) have the same minimal inducing walks and the walk \(\left( {e(l_{j-1}, a_s)}, {e(f_{j+1}, a_s)} \right)\) is a minimal inducing walk.

Case 1:  There is no \(h\) with \(1 \leq h < j\) such that \(l_h \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ a_s\) in \(G'\) or \(l_h \not \in adj(a_s,G')\).

In this case, \(l_1 \ \text{---}\!\!\!\!\succ\! \ b\) and the walk \(\omega(v_1,l_1) \mathbin{+}\left( {e(l_1, a_s)}, {e(a_s, f_{j+1})} \right)\) is an open walk given \(Cb\) which is a contradiction.

Case 2:  There is an \(h\) with \(1 \leq h < j\) such that \(l_h \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ a_s\) in \(G'\) or \(l_h \not \in adj(a_s,G')\). Choose \(h\) be as large as possible such that \(l_h \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ a_s\) in \(G'\) or \(l_h \not \in adj(a_s,G')\).

Case 2.1:  \(l_h \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ a_s\). In this case, the walk \(\omega(v_1,l_h) \mathbin{+}\left( {e(l_h, a_s)}, {e(a_s, f_{j+1})} \right)\) is an open walk given \(Cb\) which is a contradiction.

Case 2.2:  \(l_h \not \in \mathop{\mathrm{Adj}}(a_s,G')\). In this case, the walk \(\omega'(l_h,f_j)\mathbin{+}\gamma_d'(f_j, a_s)\) is a minimal inducing walk. By assumption, this walk must be in \(G\), however, this cannot be the case as \(a_s \in \mathop{\mathrm{Ant}}(a_r,G)\) which leads to a contradiction by Lemma 60.

In all cases, we have a contradiction and thus the lemma holds. ◻

Proof. Let \(G\) and \(G'\) be two separable graphs with the same adjacencies and same minimal inducing walks. let \(H=\text{\rmfamily\upshape Anterialize}(G)\) and \(H'=\text{\rmfamily\upshape Anterialize}(G')\). By Theorem 12 we have that \(G\equiv H\) and \(H\) is a separable anterial graph, and \(G'\equiv H'\) and \(H'\) is a separable anterial graph. From Lemmas 51, 52, and 56, we have that \(G\) and \(H\) have the same adjacencies and same minimal inducing walks and \(H'\) and \(G'\) have the same adjacencies and same minimal inducing walks. Thus we also have that \(H\) and \(H'\) have the same adjacencies and same minimal inducing walks. The conclusion then follows from Lemma 61 and the transitivity of equivalence. ◻

Proof. Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) be a discriminating inducing walkin that discriminates collider section \(\sigma\) on \(\omega\) and let \({v_1} \perp\!\!\!\!\perp_{G} {v_n}\ |\ {C}\). Neither \(v_1\) nor \(v_n\) is in \(\operatorname{IV}(v_1,v_n,C,G).\) Next consider a vertex \(v_k\) not on \(\sigma\) with \(1<k<n\) and \(i \neq j\). From the definition of discriminating inducing walk, \(v_k \in \mathop{\mathrm{Ant}}(\{\, v_1,v_n \,\},G)\). From ordered upward separation stability (Lemma 45), we have that \({v_1} \perp\!\!\!\!\perp_{G} {v_n}\ |\ {Cv_k}\) which implies that \(v_k\not\in \operatorname{IV}(v_1,v_n,C,G).\) Finally consider a vertex \(v_l\) on \(\sigma_j\). In this case, \(\omega\) is open given \(Cv_l\) as every collider section is either anterior to an endpoint or a vertex in \(Cv_l\). This implies that \(v_l\in \operatorname{IV}(v_1,v_n,C,G).\) ◻

Proof. Let \(G\) and \(G'\) be two separable graphs that have the same adjacencies.

The forward direction follows from the fact that every minimal discriminating inducing walkis a minimal inducing walk.

Next we consider the backward direction. Assume the lemma does not hold in the backward direction and let \(G\) and \(G'\) be two graph with the same adjacencies and the same minimal discriminating inducing walks but different minimal inducing walks. Without loss of generality, assume there is a minimal inducing walk\(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) in \(G\) such that there is no \(\omega'\) with \(\text{\rmfamily\upshape ver}({\omega'})=\left( {v}_{1},\ldots,{v}_{n} \right)\) that is a minimal inducing walkin \(G'\). Consider the minimal inducing walkdecomposition $ {_{iw}}(, G)= {, _1, , d ,}$ that contains a set of minimal discriminating inducing walks. There must be minimal discriminating inducing walks \(\gamma_i'\) in \(G'\). Next consider the walk \(\omega'= {\text{\rmfamily\upshape decomp}_{iw}}^{-1}(\{\, \gamma_1',\ldots,\gamma_d' \,\}, G')\) created by combining these minimal discriminating inducing walks. \(\omega'\) must be an inducing walk. If \(\omega'\) is a minimal inducing walkthen we have a contradiction. If \(\omega'\) is not a minimal inducing walkthen there must be a shorter minimal inducing walk\(\omega_m'\) in \(G'\) that uses a subset of vertices on \(\omega'\). Consider the decomposition $ {{iw}}(_m’, G’)={, _1’,,_e’ ,}\(. It must be the case that there are minimal discriminating inducing walks\)_i$ in \(G\). Consider the walk \(\omega_m= {\text{\rmfamily\upshape decomp}_{iw}}^{-1}(\{\, \beta_1,\ldots, \beta_e \,\}, G)\). It must be an inducing walk between \(v_1\) and \(v_n\) that uses a subset of the vertices of \(\omega\) and thus \(\omega\) is not a minimal inducing walk. This is a contradiction. Thus the backward direction must hold.

Both the forward and backward directions hold so the lemma must be true. ◻

Proof. The implication \((1)\implies(2)\) follows from Lemma 51. The implication \((1) \text{ and } (2)\implies(3)\) follows from Lemmas 52 and 56. The implication \((3)\implies(1)\) follows from Lemma 62. Finally the bi-implication \((3) \iff (4)\) follows from Lemma 63. Thus the lemma is true. ◻

Proof. Follows from Lemma [lem:combined-chracterization]. ◻

Proof. Follows from Lemma [lem:combined-chracterization]. ◻

Proof. Follows from Lemma [lem:combined-chracterization]. ◻

Proof. From Theorem 12 we replace \(G\) with \(\text{\rmfamily\upshape Anterialize}(G)\) and \(H\) with \(\text{\rmfamily\upshape Anterialize}(H)\) as the algorithm preserves equivalence. The correctness then follows from Theorem 22. ◻

Proof. The algorithm applied to \(G\) adds an edge if and only if there is an edge in \(G\) and thus the graphs have the same adjacencies. ◻

Proof. Consider a minimal inducing walk \(\gamma\) in a separable graph \(G\). We show that all internal arrowheads on \(\gamma\) are induced. Choose an arbitrary internal arrowhead at \(b\) on \(e(b,d)\) on \(\gamma\). Denote the section containing \(b\) by \(\sigma\). By Lemma 20, there is an discriminating inducing walk\(\pi\) that discriminates \(\sigma\). Denote the endpoints of \(\pi\) by \(i\) and \(j\). Because \(\pi\) is a discriminating inducing walk, \(i\not\in \mathop{\mathrm{Adj}}(j,G).\) From Theorem 9, we have that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\) where \(C=\mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\setminus \{\, i,j \,\}\). In addition, again due to the fact that \(\pi\) is a discriminating inducing walk, \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb}\). These imply that \(b\in \operatorname{IV}(i,j,C,G).\) Since \(d\in C,\) we also have \(d\not\in IV(i,j,C,G)\), which then implies that the arrowhead at \(b\) on \({e(b, d)}\) is an induced arrowhead. ◻

Proof. Consider a minimal inducing walk \(\gamma\) in separable graph \(G\). From Lemma 65 there is a walk \(\gamma'\) in \(\text{\rmfamily\upshape InducedArrowheads}(G)\) with the same vertex sequence as \(\gamma\). Again from Lemma 65, the endpoints of \(\gamma'\) are not adjacent. This fact, Lemma 66, and the fact that the algorithm only remove arrowheads that are not induced arrowheads imply that \(\gamma'\) is an inducing walk. ◻

Proof. Denote the endpoints of \(\gamma'\) by \(i\) and \(j\). By Lemma 65 we have that there is walk \(\gamma\) in \(G\) with \(\text{\rmfamily\upshape ver}({\gamma})=\text{\rmfamily\upshape ver}({\gamma'})\). If we show that all internal arrowheads on \(\gamma\) are induced arrowheads in \(G\) then we are done since \(\text{\rmfamily\upshape InducedArrowheads}(G)\) only removes arrowheads from \(G\). Suppose, for contradiction, that an internal arrowhead on \(\gamma\) at vertex \(b\) on \(e(d,b)\) is not induced.

We note that on \(\gamma'\), the edge \(e(d,b)\) is undirected since \(\gamma'\) is an inducing walk. Without loss of generality, we assume \(b\) is the closest vertex with a removed arrowhead to the endpoint of its section on its side on \(\gamma'\), i.e.\(b\) is such that on the subsection between \(b\) and an endpoint of the section that do not contain \(d\), the is no arrowhead removed. Consider the endpoint of this section that is close to \(b\) by \(b'\), and denote the vertex on \(\gamma'\) outside this section that is adjacent to \(b'\) by \(d'\). If \(b=b'\), we choose \(d'\) to be the other adjacent vertex of \(b\) than \(d\).

Notice that there exists at least a \(C\) such that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\) because \(i\) and \(j\) are not adjacent and \(G\) is separable. Since the arrowhead at \(b\) is not induced, by the contrapositive of the definition of induced arrowheads, we have that, for every \(i,j,C\), such that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {C}\), either (i) \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {Cb}\) or (ii) \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb}\) and \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cd}\).

We show that the arrowhead at \(b'\) on \(e(b',d')\) is not induced: Since \(b\) and \(b'\) are in the same section we have that \({i} \perp\!\!\!\!\perp_{G} {j}\ |\ {Cb}\iff {i} \perp\!\!\!\!\perp_{G} {j}\ |\ {Cb'}\). This implies that if case (i) holds for \(b\), the analogous of case (i) holds for \(b'\). In addition, if case (ii) holds for \(b\) then it holds that \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cb'}\).

What is left to show is if case (ii) holds for \(d\) then \({i} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {j}\ |\ {Cd'}\): Since \(G\) is separable, by Lemma 66, there is an edge between \(d\) and \(d'\). This edge cannot have an arrowhead at \(d\) since otherwise \(\gamma'\) is not the shortest self-inducing walk between \(u\) and \(v\). Therefore, regardless of whether there is an arrowhead at \(d'\) on \(e(d,d')\), if there is a connecting walk between \(i\) and \(j\) given \(Cd\), there is a connecting walk between \(i\) and \(j\) given \(Cd'\).

This completes the proof of the arrowhead at \(b'\) on \(e(b',d')\) is not induced, and consequently, there is no arrowhead at \(b'\) on this edge in \(\text{\rmfamily\upshape InducedArrowheads}(G)\). This is a contradiction since \(b'\) is an endpoint of a section on \(\gamma'\). Therefore, all internal arrowheads on \(\gamma\) are induced. ◻

Proof. Let \(\gamma\) be a minimal inducing walk in \(G\). Lemma 67 shows there is an inducing walk \(\gamma' \equiv \gamma\) in \(\text{\rmfamily\upshape InducedArrowheads}(G)\). Suppose \(\gamma'\) is not minimal. This implies that there is another walk \(\omega\) that is minimal in \(\text{\rmfamily\upshape InducedArrowheads}(G)\). From Lemma 68, there is an inducing walk in \(G\) that uses a subset of the vertices in \(\gamma\). This contradicts \(\gamma\) being minimal. Thus \(\gamma'\) must be minimal inducing walk in \(\text{\rmfamily\upshape InducedArrowheads}(G)\).

The other direction is proven with a similar argument. ◻

Proof. By Theorem 10, \(G\) does not contain a self-inducing walk, and we need to show that \(\text{\rmfamily\upshape InducedArrowheads}(G)\) does not contain a self-inducing walk. Suppose, for contradiction, that there is a self-inducing walk \(\gamma'\) in \(\text{\rmfamily\upshape InducedArrowheads}(G)\). Assume, without loss of generality, that \(\gamma'\) is the shortest such walk, and denote the endpoints of \(\gamma'\) by \(u\) and \(v\). This implies that \(\gamma'\) is a minimal inducing walk.

We note, by Lemma 65, that \(G\) and \(\text{\rmfamily\upshape InducedArrowheads}(G)\) have the same adjacencies. Hence, each walk \(\nu'\) in \(\text{\rmfamily\upshape InducedArrowheads}(G)\) has a corresponding walk with the same vertices and edges, denoted by \(\nu\), in \(G\) on which some arrowheads are potentially removed on \(\nu'\). Also, each internal vertex of \(\gamma'\) is an anterior to one of its endpoints. For each vertex \(w\) on \(\gamma'\), consider the anterial walk from \(w\) to an endpoint of \(\gamma'\), denoted by \(\nu'_w\), such that \(\nu'_w\) has the fewest number of arrowheads removed among such anterior walks. Consider the subgraph of \(\text{\rmfamily\upshape InducedArrowheads}(G)\) consisting of the vertices of \(\gamma'\) and the vertices of all the walks \(\nu'_w\) for every internal vertex \(w\) of \(\gamma'\). Call this subgraph \(K'\).

Below we show that in the induced subgraph \(K\) of \(G\) with respect to the vertices of \(K'\), there exists an arrowhead at \(b\) on \(e(b,d)\) in \(K\) that does not exist in \(K'\), but is induced. This leads to a contradiction with the arrowhead not existing in \(K'\).

Again, we note, by Lemma 65, that \(K\) and \(K'\) have the same adjacencies, and any arrowhead in \(\text{\rmfamily\upshape InducedArrowheads}(G)\) exists in \(G\). Since \(\gamma'\) is a minimal inducing walk, by Lemma 69, there exists a walk \(\gamma\) in \(G\) with the same vetices that is a minimal inducing walk. Since all arrowheads on \(\gamma\) are induced in \(G\), as proven in Lemma 66, the arrowhead at \(b\) must be on an edge in \(K'\) that is not on \(\gamma\).

If vertices at which the arrowhead is removed are in \(\mathop{\mathrm{PropAnt}}(\{\, u,v \,\},G)\) then \(\gamma\) is self-inducing in \(G\), which is not possible. Hence, choose \(e(b,d)\) such that the arrowhead at \(b\) is removed and \(b\notin\mathop{\mathrm{PropAnt}}(\{\, u,v \,\},G)\).

Consider a vertex \(i\) in \(\gamma\) that is an anterior of \(b\) in the anterior walk from \(i\) to \(\{u,v\}\) in \(\text{\rmfamily\upshape InducedArrowheads}(G)\) (\(i\) can be \(b\) itself). Denote the section of \(i\) on \(\gamma\) by \(\rho\). Let \(C=\mathop{\mathrm{PropAnt}}(\{u,v\},G)\cup\text{\rmfamily\upshape ver}({\gamma})\setminus \rho\), i.e, be all proper anteriors of \(u\) and \(v\) and vertices of \(\gamma\) except the vertices in the section that is an anterior of \(b\).

First, \({u} \perp\!\!\!\!\perp_{G} {v}\ |\ {C}\) since otherwise \(i\in\mathop{\mathrm{PropAnt}}(\{u,v\},G)\), which implies that \(b\in\mathop{\mathrm{PropAnt}}(\{u,v\},G)\).

Secondly, let \(b\) be the closest vertex to \(i\). Clearly, \({u} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {v}\ |\ {Cb}\).

Thirdly, let \(b\) be the closest vertex to \(u\). The only option where \(d\) can be on a connecting walk between \(u\) and \(v\) given \(Cd\) is via the anterior walk from \(d\) to \(u\). However \(d\) is on a non-collider section in this walk and cannot make a connecting walk. Therefore, \({u} \perp\!\!\!\!\perp_{G} {v}\ |\ {Cd}\).

These imply that the arrowhead at \(b\) is indeed induced, which is a contradiction. ◻

Proof. Since, by Lemma 70, \(G\) and \(\text{\rmfamily\upshape InducedArrowheads}(G)\) are separable, by Theorem 19, it is enough to show that \(G\) and \(\text{\rmfamily\upshape InducedArrowheads}(G)\) have the same adjacencies and minimal inducing walks. The former is Lemma 65 and the latter is Lemma 69. ◻

Proof. If two graphs \(G\) and \(G'\) are separation equivalent and separable then they must have the same adjacencies and induced arrowheads by Theorem 24. This implies that \(\text{\rmfamily\upshape InducedArrowheads}(G)=\text{\rmfamily\upshape InducedArrowheads}(G')\). If \(G'\not \equiv G\) then, again by Theorem 24, they must have different adjacencies or induced arrowheads with implies that \(\text{\rmfamily\upshape InducedArrowheads}(G) \not \equiv \text{\rmfamily\upshape InducedArrowheads}(G')\). This proves that is a canonical representation function for separable graphs. Then, by Lemma 70 and Theorem 25, it follows that also a canonical projection function. ◻

Proof. Let \(G\) be a separable graph. Every graph in \(\text{\rmfamily\upshape Largest}(G)\) is separable and equivalent to \(G\). Let \(H,H' \in \text{\rmfamily\upshape Largest}(G)\). By Theorem 24, \(H\) and \(H'\) have the same adjacencies and same induced arrowheads. Consider the graph \(\text{\rmfamily\upshape InducedArrowheads}{G}\). It has the same adjacencies and induced arrowheads. Furthermore, all of its arrowheads are induced arrowheads so it must be in \(\text{\rmfamily\upshape Largest}(G)\). If any of the edges in \(H\) or \(H'\) have an arrowhead that is not in \(\text{\rmfamily\upshape InducedArrowheads}{G}\) then it is not in \(\text{\rmfamily\upshape Largest}(G)\) thus \(H=H'=\text{\rmfamily\upshape InducedArrowheads}{G}\). ◻

Proof. Let \(G\) be a separable graph. From Lemma 70, \(G'=\text{\rmfamily\upshape InducedArrowheads}(G)\) is separable and from Theorem 25, \(G\equiv G'\).

From Theorem 12, \(G''= \text{\rmfamily\upshape Anterialize}(G')\) is an anterial graph equivalent to \(G'\). Thus we also have, \(G''\equiv G\). From the fact that the algorithm only removes arrowheads and the fact that these graphs are equivalent it must be the case that \(G'=G''\) and thus \(G'\) is an anterial graph. ◻

Proof. From Lemma 46, if \(C\) is a minimal separating set for \(i\) and \(j\) in graph \(G\) then \(C\subseteq \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\). Thus any minimal separating set is an anterior separating set. ◻

Proof. let \({e(d, b)}\) have an induced arrowhead at \(b\) in a graph \(G\). From the definition of induced arrowheads, there is some pair of vertices \(p\) and \(q\) and vertex set \(D\) such that \(b\in \operatorname{IV}(p,q,D,G)\) and \(d\not \in \operatorname{IV}(p,q,D,G)\). From \(b\in \operatorname{IV}(p,q,D,G)\), we have that \({p} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\) and \({p} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {q}\ |\ {Db}\).

Case 1:  \(d\in \mathop{\mathrm{Ant}}(\{\, p,q \,\},G)\setminus \{\, p,q \,\}\). In this case, the lemma holds for vertices \(i=p\) and \(j=q\) and vertex set \(C=D\) and note that using this assignment we have \(b\in \operatorname{IV}(i,j,C,G)\) and \(d\in \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\). Thus the lemma holds in this case.

Case 2:  \(d\not\in \mathop{\mathrm{Ant}}(\{\, p,q \,\},G)\setminus \{\, p,q \,\}\). From \(d\not\in \operatorname{IV}(p,q,D,G)\), it must be the case that \({p} \perp\!\!\!\!\perp_{G} {q}\ |\ {Dd}\). From \({p} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\) and \({p} \perp\!\!\!\!\perp_{G} {q}\ |\ {Dd}\), and weak transitivity, it must be the case that \({p} \perp\!\!\!\!\perp_{G} {d}\ |\ {D}\) or \({d} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\). Without loss of generality, assume that \({d} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\). From \({p} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\), \({d} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\), and composition we have \({dp} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\) and, by weak union we have \({d} \perp\!\!\!\!\perp_{G} {q}\ |\ {Dp}\). From \({p} \perp\!\!\!\!\perp_{G} {q}\ |\ {D}\) and \({p} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {q}\ |\ {Db}\) and Lemma 43, there is a walk \(\gamma_q\) between \(b\) and \(q\) open given \(Dp\) and weakly into \(b\). In this case, the walk \(\left( {e(d, b)} \right)\mathbin{+}\gamma_q\) is open given \(Dpb\) which implies that \({d} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {q}\ |\ {Dpb}\). Thus we have shown \({d} \perp\!\!\!\!\perp_{G} {q}\ |\ {Dp}\) and \({d} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {q}\ |\ {Dpb}\) which implies that \(b\in IV(d,q,Dp,G)\). In this case, let \(i=d\), \(j=q\) and \(C=Dp\) and note that using this assignment we have \(b\in \operatorname{IV}(i,j,C,G)\) and \(d\in \mathop{\mathrm{Ant}}(\{\, i=d,j \,\},G)\). Thus the lemma holds in this case. ◻

Proof. Assume that that claim is not true and that there are separable vertices \(a\) and \(b\) in graph \(G\) such that \({a} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {b}\ |\ {C}\) where \(C=\text{\rmfamily\upshape iAdj}(a,b,G)\cap \mathop{\mathrm{Ant}}(ab,G)=\text{\rmfamily\upshape aiAdj}(a,b,G)\). This implies that there is a connecting walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) with \(v_1=a\) and \(v_n=b\) that is open given \(C\). We consider three possible types of walks for \(\omega\).

Case 1:  \(\omega\) consist of a single edge \({e(a, b)}\). In this case, by Lemma 9, \(a\) and \(b\) are not separable. This is a contradiction with the assumption that \(a\) and \(b\) are separable.

Case 2:  \(\omega\) is a collider walk. In this case, every collider section on \(\omega\) must be anterior to the endpoints and thus is a self-inducing walk. This implies, by Theorem 10, that \(a\) and \(b\) are not separable. This is again a contradiction.

Case 3:  \(\omega\) is not a collider walk. In this case there is some non-trivial maximal trek. let \(\omega(v_{i-1},v_{j+1})\) with \(i\leq j\) be the maximal trek closest to \(a=v_1\) on \(\omega\). By Lemma 12, we have that \(v_i \in \mathop{\mathrm{Ant}}(abC,G)\). Furthermore, from \(C=\text{\rmfamily\upshape aiAdj}(a,b,G) \subseteq \mathop{\mathrm{Ant}}(\{\, a,b \,\},G)\) we have \(v_i \in \mathop{\mathrm{Ant}}(\{\, a,b \,\},G)\). Next, consider the subwalk \(\omega(a,v_i)\). The subwalk is a collider walk. From the fact that \(\omega\) is a connecting walk given \(C\), every collider section on the subwalk contains a vertex of \(C\). From \(C=\text{\rmfamily\upshape aiAdj}(a,b,G) \subseteq \mathop{\mathrm{Ant}}(\{\, a,b \,\},G)\), every collider section is anterior to \(\{\, a,b \,\}\) and thus \(v_i \in \text{\rmfamily\upshape iAdj}(a,b,G)\).

Thus \(v_i\in C\) and \(\omega\) is not a connecting walk as a non-collider section contains a vertex in \(C\). This is a contradiction.

In each case we have a contradiction so the claim must hold. ◻

Proof. Let \(G=\left( V,E \right)\) be an anterial graph and for \(a,b\in V\) it is the case that \(a\neq b\).

Case 1:  \(a \mathrel{\mathrel{\parallel}_G}b\). In this case, by definition, we have that \(a \mathrel{\not\sim_G}b\), \(a \mathrel{\not <_G}b\), and \(b \mathrel{\not <_G}a\) and the property is exclusive.

Case 2:  \(a \mathrel{\sim_G}b\). First, by definition, we have that \(a \mathrel{\mathrel{\curlyvee}_G}b\). Next, due the fact that \(a \mathrel{\sim_G}b\) and that \(G\) contains no semi-directed cycle, we must have \(a \mathrel{\not <_G}b\) and \(b \mathrel{\not <_G}a\). In this case, the property is exclusive.

Case 3:  \(a \mathrel{<_G}b\) or \(b \mathrel{<_G}a\). Without loss of generality, assume \(a \mathrel{<_G}b\). In this case, by definition, we have that \(a \mathrel{\mathrel{\curlyvee}_G}b\). It cannot be the case that \(a \mathrel{\sim_G}b\) or \(b \mathrel{<_G}a\) otherwise, in either case, there would be a semi-directed cycle and \(G\) contains no semi-directed cycle. In this case, the property is exclusive.

Thus exactly one of the following holds for any distinct pair of vertices \(a,b\in V\), \(a \mathrel{\mathrel{\parallel}_G}b, a\mathrel{\sim_G}b, a\mathrel{<_G}b\), and \(b \mathrel{<_G}a\) and thus the proposition holds. ◻

Proof. Let \(G\) be an anterial graph such that \(a\in \mathop{\mathrm{Adj}}(b,G)\).

Case (i):  For the forward direction, let \(a \mathrel{\sim_G}b\). If \(a \ \text{---}\!\!\!\!\succ\! \ b\), or \(a \ \!\prec\!\!\!\!\text{---}\ b\) then there would be a semi-directed walk which contradicts \(G\) being anterial. Similarly, if \(a \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ b\), then there would be a bidirected edge with an endpoint anterior to its other endpoint which also contradicts \(G\) being anterial. Thus the edge must be oriented \(a \ \text{---}\ b\). For the other direction, assume \(a \ \text{---}\ b\). In this case, the walk containing this edge is an undirected walk between \(a\) and \(b\) and thus \(a\mathrel{\sim_G}b\).

Case (ii):  For the forward direction, let \(a \mathrel{\mathrel{\parallel}_G}b\). By Lemma 72, we have that \(a\) and \(b\) are not ordered which rules out \(a \ \text{---}\!\!\!\!\succ\! \ b\) and \(a \ \!\prec\!\!\!\!\text{---}\ b\). Again, by Lemma 72, we have that \(a \mathrel{\not\sim_G}b\) which rules out \(a \ \text{---}\ b\). This implies that \(a \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ b\). For the other direction, let \(a \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ b\). If either \(a \mathrel{<_G}b\), \(b \mathrel{<_G}a\) or \(a \mathrel{\sim_G}b\) there would be a bidirected edge with an endpoint anterior to its other endpoint which contradicts \(G\) being anterial. Thus \(a \mathrel{\mathrel{\parallel}_G}b\).

Case (iii):  For the forward direction, let \(a \mathrel{<_G}b\). By Lemma 72, we have that \(b \mathrel{\not <_G}a\) and \(a \mathrel{\not\sim_G}b\) which rules out \(a \ \!\prec\!\!\!\!\text{---}\ b\) and \(a \ \text{---}\ b\). If \(a \ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ b\) then there would be a bidirected edge with an endpoint anterior to its other endpoint which cannot be the case due to \(G\) being anterial. This implies that \(a \ \text{---}\!\!\!\!\succ\! \ b\) For the other direction, let \(a \ \text{---}\!\!\!\!\succ\! \ b\). This implies that \(a \mathrel{<_G}b\).

Case (iv):  Similar to case (iii). ◻

Proof. Let \(G\) be an anterial graph containing separable vertices \(a\) and \(b\) such that \(a \mathrel{\sim_G}b\). Suppose that the claim does not hold and that \({a} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {b}\ |\ {C}\) where \(C=\text{\rmfamily\upshape aAdj}(a,G)\). This implies that there is a walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) where \(v_1=a\) and \(v_n=b\) that is connecting given \(C\). Note that \(v_2 \neq b\), otherwise \(a\) and \(b\) are not separable.

From Lemma 72, it must be the case that \(a \mathrel{\not <_G}b\), \(b \mathrel{\not <_G}a\), and \(a \mathrel{\mathrel{\curlyvee}_G}b\).

Case 1:  \(a \ \text{---}\!\!\!\!\succ\! \ v_2\) or \(a\ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_2\). From anterial endmark property, Lemma 31, we have that \(v_2 \not\in \mathop{\mathrm{Ant}}(a, G)\). As \(a\mathrel{\sim_G}b\) we also have \(v_2 \not\in \mathop{\mathrm{Ant}}(b,G).\) There must be some collider section \(\sigma_i\) for \(1<i<m\) as \(\sigma_2 \not\in \mathop{\mathrm{Ant}}(ab,G)\) and this section cannot contain a vertex in \(C\). This implies that the walk \(\omega\) is not a connecting walk given \(C\).

Case 2:  \(a \ \text{---}\ v_2\) or \(a \ \!\prec\!\!\!\!\text{---}\ v_2\). In either case, \(v_2\) is on a non-collider section of \(\omega\) and \(v_2\in C\). This implies that the walk \(\omega\) is not a connecting walk given \(C\).

In either case, the walk \(\omega\) is not a connecting walk given \(C\) so the claim holds. ◻

Proof. Let \(G\) be an anterial graph containing separable vertices \(a\) and \(b\) such that \(b \mathrel{<_G}a\). Suppose that the claim does not hold and that \({a} { \perp\!\!\!\!\perp \raisebox{0.16em}{\smallsetminus} }_{G}\ {b}\ |\ {C}\) where \(C=\text{\rmfamily\upshape aAdj}(a,G)\). This implies that there is a walk \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) and \(\text{\rmfamily\upshape sec}({\omega})=\left( {\sigma}_{1}, \ldots, {\sigma}_{m} \right)\) where \(v_1=a\) and \(v_n=b\) that is connecting given \(C\). Note that \(v_2 \neq b\), otherwise \(a\) and \(b\) are not separable.

From Lemma 72, it must be the case that \(a \mathrel{\not <_G}b\), \(a \mathrel{\not\sim_G}b\), and \(a \mathrel{\mathrel{\curlyvee}_G}b\).

We show \({a} \perp\!\!\!\!\perp_{G} {b}\ |\ {\text{\rmfamily\upshape aAdj}(a,G)}\).

Case 1:  \(a \ \text{---}\!\!\!\!\succ\! \ v_2\) or \(a\ \!\prec\!\!\!\!\text{---}\!\!\!\!\succ\! \ v_2\). From the anterial endmark property, Lemma 31, we have that \(v_2 \not\in \mathop{\mathrm{Ant}}(a, G)\). As \(b \mathrel{<_G}a\) and \(G\) is anterial, we also have \(v_2 \not\in \mathop{\mathrm{Ant}}(b,G).\) There must be some collider section \(\sigma_i\) for \(1<i<m\) as \(\sigma_2 \not\in \mathop{\mathrm{Ant}}(ab,G)\) and this section cannot contain a vertex in \(C\). This implies that the walk \(\omega\) is not a connecting walk given \(C\).

Case 2:  \(a \ \text{---}\ v_2\) or \(a \ \!\prec\!\!\!\!\text{---}\ v_2\). In either case, \(v_2\) is on a non-collider section of \(\omega\) and \(v_2\in C\). This implies that the walk \(\omega\) is not a connecting walk given \(C\).

In either case (1) or (2), the walk \(\omega\) is not a connecting walk given \(C\) so the claim must hold. ◻

Proof. Let \(G_{final}=\text{\rmfamily\upshape SGI}({I}{(G^*)})\) and \(G\) denote that current graph at various steps of running the algorithm. Initially, \(G\) is the complete graph. An edge \({e(a, b)}\) is removed only if a set \(C\) is found and \({a} \perp\!\!\!\!\perp_{{I}{(P^*)}} {b}\ |\ {C}\). This implies that \(a\) and \(b\) are separable in \(G^*\). ◻

Proof. Let \(G_{final}=\text{\rmfamily\upshape SGI}({I}{(G^*)})\) and \(G\) denote that current graph at various steps of running the algorithm. Initially, \(G\) is the complete graph and \(\mathop{\mathrm{Ant}}(i,G)=V\setminus i\) so the claim holds. The claim then follows from the soundness of the orientation rule used to add arrowheads to edges (Proposition 23). ◻

Proof. This follows from Lemmas 76 and 77. ◻

Proof. Assume \(a \mathrel{\approx}_{G^*} b\), \(G_{final}=\text{\rmfamily\upshape SGI}({I}{(G^*)})\) and \(a\in \mathop{\mathrm{Adj}}(b,G_{final})\). Suppose the claim is not true and that the edge \({e(a, b)}\) in \(G_{final}\) has an arrowhead at \(a\), \(b\) or both \(a\) and \(b\). Without loss of generality, assume there is one at \(a\). The edge must have an induced arrowhead at \(a\) in \({I}{(P^*)}\). This implies that there exists \(\left( i, j, C \right)\) such that \(a\in IV(i,j,C,G^*)\). This, however, cannot be the case due to Proposition 17. Thus the claim must be true. ◻

Proof. Let \(\omega\) with \(\text{\rmfamily\upshape ver}({\omega})=\left( {v}_{1},\ldots,{v}_{n} \right)\) be a discriminating inducing walkthat discriminates collider section \(\sigma=\left( v_i,v_j \right)\) in \(G^*\) and assume that removed the edge \({e(v_1, v_n)}\). The fact that the edge \({e(v_{1}, v_{n})}\) was removed implies that there is a set \(C\) that separates \(v_1\) and \(v_n\) in \(G^*\) that was used by the algorithm to remove the edge. From Proposition 21, every vertex on a discriminated section of a discriminating inducing walkis an inducing vertex for the endpoints of the discriminating inducing walk(i.e., in \(\operatorname{IV}(v_1,v_n,C,G^*)\)) and that every other vertex on \(\omega\) is not an inducing vertex (i.e., not in \(\operatorname{IV}(v_1,v_n,C,G^*)\)). This implies that the edge closed to \(\sigma\) on the walk between \(a\) and \(\sigma\) has an induced arrowhead at \(\mathop{\mathrm{first}}(\sigma)\). This implies that the algorithm will add these arrowheads after removing the edge \({e(v_{1}, v_{n})}\). ◻

Proof. We show this algorithmic invariant inductively on the length of the trace of \(\text{\rmfamily\upshape SGI}(G^*)\).

For the base case we consider the initial graph. This initial graph is a simple complete undirected graph and thus satisfies the anterial endmark property. By Lemma 31 the graph is anterial.

For the inductive case we assume that the current graph is anterial and show that after identifying a separating set \(C\) for \(i\) and \(j\), removing the edge between \(i\) and \(j\) and orienting, the resulting graph is again anterial. First note that the resulting graph is simple. Consider the set \(\operatorname{IV}=\operatorname{IV}(i,j,C, G^*)\) and \(D=V \setminus \operatorname{IV}\). Any new endmark is at an endpoint of an edge \({e(c, d)}\) with \(c\in D\) and \(d \in \operatorname{IV}\) with the new arrowhead at \(d\). The resulting graph satisfies the anterial endmark property as (1) for new endmarks (necessarily arrowheads), every edge between a vertex in \(D\) and a vertex in \(\operatorname{IV}\) has an arrowhead endmark at the vertex in \(\operatorname{IV}\) and thus there can be no anterior walk violating the anterial endmark property, (2) for old endmarks, the addition of an arrowhead does not create any new anterial walks. Thus, by Lemma 31 the graph is anterial. ◻

Proof. Let \(G^*\) be an essentially separable graph, \(G_{final}=\text{\rmfamily\upshape SGI}({I}{(P^*)})\).

let \(G\) be a separable anterial graph such that \(G \equiv G^*\); one exists due to the fact that \(G^*\) has an equivalent separable graph and Theorem 12.

First we recast the lemma in terms of separation completeness. A graph \(G_{final}\) is separation complete with respect to graph \(G\) and vertex set \(A\subseteq V\) if for all pairs of distinct vertices \(a,b \in A\), if \(a\not\in \mathop{\mathrm{Adj}}(b,G)\) then \(a \not\in \mathop{\mathrm{Adj}}(b,G_{final})\). Thus the lemma holds if we can show that \(G_{final}\) is separation complete with respect to \(G\) and \(V\).

Next, note that \(\left( A(G), \subseteq \right)\) is well-founded as \(A(G)\) is a finite set and \(\subseteq\) is a partial order over \(A(G)\). We prove the claim by well-founded induction on \(A(G)\) with respect to \(\subset\). In particular, we prove that \(G_{final}\) is separation complete with respect to \(G\) and \(A_j\) under the induction hypothesis that \(G_{final}\) is separation complete with respect to \(G\) and all \(A_i \subset A_j\).

Define \(\max(A)=\{\, {a}\in {A}\ | \ {\forall b\in A, b \mathrel{\lessapprox}_Ga} \,\}.\) Let \(A_i = A_j \setminus \max(A_j)\). The set \(A_i\) is an ancestral set, that is, \(A_i\in A(G)\). By induction assumption, all edges between separable vertices in \(A_i\) have been removed. Thus we need only consider pairs of vertices \(a,b \in A_j\) that are separable in \(G\) and such that at least one of the vertices is in the set \(\max(A_j)\). Without loss of generality, assume \(a\in \max(A_j)\).

Case 1:  \(a \mathrel{\approx_G}b\). In this case, from Lemmas 78 and 75 we know that \(\text{\rmfamily\upshape aAdj}(a,G_{final})\) and \(\text{\rmfamily\upshape aAdj}(b,G_{final})\) separate \(a\) and \(b\) and at least one of them must be smaller then \(\text{\rmfamily\upshape SepSetBound}(G_{final})\).

Case 2:  \(a \mathrel{<_G}b\) or \(b \mathrel{<_G}a\). Without loss of generality, assume \(b \mathrel{<_G}a\). In this case, from Lemmas 78 and 74 we know that \(\text{\rmfamily\upshape aAdj}(a,G_{final})\) separates \(a\) and \(b\) and that the set is smaller then \(\text{\rmfamily\upshape SepSetBound}(G_{final})\).

Case 3:  \(a \mathrel{\mathrel{\parallel}_G}b\). Let \(A_b= A_j \setminus [a]_\approx^G\) and \(A_a = A_j \setminus [b]_\approx^G\). In this case we have that \(b\in A_b\), \(a\in A_a\), \(A_a \subset A_j\), \(A_b \subset A_j\), \(A_a\in A(G)\), and \(A_b\in A(G)\).

From Proposition 28, we know that \({a} \perp\!\!\!\!\perp_{G} {b}\ |\ {C}\) when \(C=\text{\rmfamily\upshape aiAdj}(a,b,G)\) and when \(C=\text{\rmfamily\upshape aiAdj}(b,a,G)\).

Without loss of generality, we show that \(\text{\rmfamily\upshape aiAdj}(a,b,G_{final}) \supseteq \text{\rmfamily\upshape aiAdj}(a,b,G)\).

Suppose that this is not the case and there is a vertex \(d\in \text{\rmfamily\upshape aiAdj}(a,b,G) \setminus \text{\rmfamily\upshape aiAdj}(a,b,G_{final})\).

Case 3.1:  \(d=b\). This cannot be the case as there would be a self-inducing walk between \(a\) and \(b\) and \(a\) and \(b\) would not be separable.

Case 3.2:  \(d\in \text{\rmfamily\upshape aAdj}(a,G)\). In this case, by Lemma 78, we have that \(\text{\rmfamily\upshape aAdj}(a,G_{final})\subseteq \text{\rmfamily\upshape aAdj}(a, G)\) so this cannot be the case.

Case 3.3:  \(d \in \text{\rmfamily\upshape aiAdj}(a,b,G)\setminus \text{\rmfamily\upshape aAdj}(a,G)\). In this case, there must be an inducing walk between \(a\) and \(d\) that is open given \(b\) in \(G\). Let \(\omega\) be a minimal inducing walk between \(a\) and \(d\) in \(G\) that is open given \(b\). There is a walk \(\omega'\) in \(G_{final}\) with the same vertex sequence. We show that \(\omega'\) is an inducing walk open given \(b\) in \(G_{final}\).

From Lemma 79, we know that every collider section on \(\omega\) corresponds to an undirected walk on \(\omega'\).

From Lemma 12, every vertex is anterior to either \(a\) or \(b\) and thus every vertex on \(\omega\) is in \(A_j\) as,

From Lemma 20, every collider section on \(\omega\) is discriminated by some discriminating inducing walkthat is a subwalk of \(\omega\).

Consider a discriminating inducing walkbetween \(v_i\) and \(v_k\) on \(\omega\) that discriminates a section \(\sigma\) and let \(A_{ik}=\mathop{\mathrm{Ant}}(\{\, v_i,v_k \,\},G)\). Clearly the set is an anterior set in \(G\) (i.e., \(A_{ik}\in A(G)\)).

We know that \(\sigma \cap A_{ik}=\emptyset\). This implies that \(A_{ik}\subseteq A_j\). From the induction hypothesis, the edge between \(v_i\) and \(v_j\) has been removed. By Lemma 80, The arrowheads into \(\sigma\) on \(\omega\) are oriented in \(\omega'\). This implies that \(\omega'\) is an inducing walk in \(G_{final}\). Finally, by Lemma 77, \(d\in \text{\rmfamily\upshape aiAdj}(a,b, G_{final}).\) This implies that \(\text{\rmfamily\upshape aiAdj}(a,b,G_{final})\subseteq \text{\rmfamily\upshape aiAdj}(a,b,G)\).

From this it must be the case that the edge between \(a\) and \(b\) must be removed in \(G_{final}\) as there is a subset of \(\text{\rmfamily\upshape aiAdj}(a,b,G)\) which will be found as \(socs \geq \text{\rmfamily\upshape SepSetBound}(G_{final})>|\text{\rmfamily\upshape aiAdj}(a,b,G)|\). ◻

Proof. Assume \(G^*\) is an essentially separable graph. Let \(G^*_{sep}\equiv G^*\) be a separable graph equivalent to \(G^*\), \(G_{SGI}=\text{\rmfamily\upshape SGI}({I}{(G^*)})\) and \(G_{IND}=\text{\rmfamily\upshape InducedArrowheads}(G^*_{sep})\).

We show \(\text{\rmfamily\upshape SGI}({I}{(G^*)})=\text{\rmfamily\upshape InducedArrowheads}(G^*_{sep})\), that is, \(G_{SGI}=G_{IND}\).

First we show that \(G_{SGI}\) and \(G_{IND}\) have the same adjacencies. From Lemma 76 we have \(\text{\rmfamily\upshape ADJ}(G_{SGI}) \supseteq \text{\rmfamily\upshape ADJ}(G^*_{sep})\) and from Lemma 82 we have \(\text{\rmfamily\upshape ADJ}(G_{SGI}) \subseteq \text{\rmfamily\upshape ADJ}(G^*_{sep})\). Thus \(G_{SGI}\) and \(G^*_{sep}\) have the same adjacencies. Next, \(G_{IND}\) and \(G^*_{sep}\) have the same adjacencies and minimal inducing walks by Theorems 26 and 19. Combining these facts we have that \(G_{SGI}\) and \(G_{IND}\) have the same adjacencies.

Second, we show that \(G_{SGI}\) and \(G_{IND}\) have the same arrowheads.

We identify the arrowheads in \(G_{IND}\) with induced arrowheads in \(G^*_{sep}\). By construction, \(G_{IND}\) has an arrowhead at \(b\) on edge \({e(d, b)}\) if and only if \({e(d, b)}\) has an induced arrowhead at \(b\) in \(G^*_{sep}\).

Next we identify the arrowheads in \(G_{SGI}\) with induced arrowheads in \(G^*_{sep}\).

Every arrowhead in \(G_{SGI}\) is to due to an induced arrowhead in \({I}{(G^*)}\), or equivalently, \({I}{(G^*_{sep})}\). Next we show that if edge \({e(d, b)}\) has in induced arrowheadat \(b\) in \(G^*_{sep}\) then there is an edge with \({e'(d, b)}\) in \(G_{SGI}\) with an arrowhead at \(b\). From the argument above, there must be an edge \({e'(d, b)}\) in \(G_{SGI}\). From Lemma 71, there exist vertices \(i\) and \(j\) and vertex set \(D\) such that \(b\in \operatorname{IV}(i,j,D,G^*_{sep})\) and \(d\in \mathop{\mathrm{Ant}}(\{\, i,j \,\},G)\). At some stage, the algorithm will identify a minimal separating set \(C\) for \(i\) and \(j\). After identifying the set \(C\) that separates \(i\) and \(j\) the algorithm will add the arrowhead at \(b\) on edge \({e'(d, b)}\) due to the fact that it will, determine that \(d\not\in \operatorname{IV}(i,j,G_{SGI})\) by testing \({i} \perp\!\!\!\!\perp_{G^*} {j}\ |\ {Cd}\) which must hold by Lemma 45. This implies that in \(G_{SGI}\) there is an arrowhead at \(b\) on edge \({e(d, b)}\) if and only if \({e(d, b)}\) has an induced arrowhead at \(b\) in \(G^*_{sep}\). This implies that \(G_{SGI}\) and \(G_{IND}\) have the same arrowheads.

From the fact that \(G_{SGI}\) and \(G_{IND}\) are simple graphs, have the same adjacencies and same arrowheads we have that \(G_{SGI}=G_{IND}\). ◻

Proof. Assume \(G^*\in \mathcal{E}({\cal G}_{sep})\) is an essentially separable graph and that \({I}{(P^*)}\) provides perfect testing with respect to \(G^*\).

Let \(G^*_{sep}\equiv G^*\) be a separable graph equivalent to \(G^*\), \(G_{SGI}=\text{\rmfamily\upshape SGI}({I}{(P^*)})\) and \(G_{IND}=\text{\rmfamily\upshape InducedArrowheads}(G^*_{sep})\). From perfect testing, we have \(\text{\rmfamily\upshape SGI}({I}{(P^*)}) = \text{\rmfamily\upshape SGI}({I}{(G^*_{sep})})\). From Theorem 30, we have \(\text{\rmfamily\upshape SGI}({I}{(P^*)})=\text{\rmfamily\upshape InducedArrowheads}(G^*_{sep})\). From Theorem 26, for all separable graphs \(G,G'\) it is the case that \(\text{\rmfamily\upshape SGI}({I}{(G)}) = \text{\rmfamily\upshape SGI}({I}{(G')})\) if and only if \(G \equiv G'\). Thus if \(G^*\in \mathcal{E}({\cal G}_{sep})\) then \(\text{\rmfamily\upshape SGI}\) identifies the equivalence class \(\left[{G^*}\right]_{\mathcal{E}({\cal G}_{sep})}\) under perfect testing. ◻

Proof. Let \(G^*\) be separable and \(P^*\) provide perfect testing for \(G^*\). Let \(G_{final}= \text{\rmfamily\upshape SGI}({I}{(P^*)})\) and note that \(G=G_{final}= \text{\rmfamily\upshape InducedArrowheads}(G^*)\) by Corollary 6. In this case, the algorithm terminates when \(socs \geq \text{\rmfamily\upshape SepSetBound}(G_{final})\). This implies that we consider at most \(O(|V|^{\text{\rmfamily\upshape SepSetBound}(G)})\) independence tests to guarantee that edges between separable pairs of vertices have been removed. In addition, the determination of the set of inducing vertices for a separated pair of vertices is bounded by \(O(|V|).\) Thus the total number of independence tests is bounded by \(O(|V|^{\text{\rmfamily\upshape SepSetBound}(G)+1})\). ◻