$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$. From Observation 5.1, $M$
has the v-structures of $M_{1}$ and $M_{2}$. Other than that, it can only have
the v-structures that involve an edge with endpoints $r_{1}$ and $r_{2}$.
There are three possibilities: either $r_{1}-r_{2}\in M$ or $r_{2}\rightarrow
r_{1}\in M$ or $r_{1}\rightarrow r_{2}\in M$.

Suppose $r_{1}-r_{2}\in M$. Then, there cannot be any v-structure with an edge
with endpoints $r_{1}$ and $r_{2}$, because a v-structure contains directed
edges, and $r_{1}-r_{2}$ is undirected. This implies that if $r_{1}-r_{2}\in
M$ then the only v-structures $M$ can have are the v-structures of $M_{1}$ and
$M_{2}$, i.e., $M$ follows eq. 15.

Suppose $r_{2}\rightarrow r_{1}\in M$. Since
$M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$, we can partition the set of neighbors
of $r_{1}$ in $G_{1}$ into $X$ and $X^{\prime}$ such that $X=\\{x:x-r_{1}\in
M_{1}\\}$ is a set of $i$ nodes, and
$X^{\prime}=\\{x^{\prime}:r_{1}\rightarrow x^{\prime}\in M_{1}\\}$ of
$\delta_{1}-i$ nodes. From Lemma 2.7, for $x^{\prime}\in X^{\prime}$,
$r_{1}\rightarrow x^{\prime}\in M$. Since $r_{2}\rightarrow r_{1}\in M$, from
item 1 of Theorem 3.1, for $x\in X$, either $r_{1}\rightarrow x\in M$ or
$x\rightarrow r_{1}\in M$, otherwise, $r_{2}\rightarrow r_{1}-x$ is an induced
subgraph in $M$, contradicting item 1 of Theorem 3.1. If for two distinct
$x_{1},x_{2}\in X$, $x_{1}\rightarrow r_{1},x_{2}\rightarrow r_{1}\in M$, then
we get a v-structure $x_{1}\rightarrow r_{1}\leftarrow x_{2}$ in $M$ such the
nodes of the v-structure are in $V_{G_{1}}$, but the v-structure is not in
$M_{1}$, implying $\mathcal{V}(M[V_{G_{1}}])\neq\mathcal{V}(M_{1})$, which
further implies $\mathcal{P}(M,V_{G_{1}})\neq M_{1}$, a contradiction. This
implies that there exists at most one $x\in X$ such that $x\rightarrow
r_{1}\in M$. If there is no $x\in X$ such that $x\rightarrow r_{1}\in M$ then
there won’t be any v-structure in $M$ with endpoints $r_{1}$ and $r_{2}$, and
in this case, $M$ contains only the v-structures of $M_{1}$ and $M_{2}$, as in
eq. 15. If there exists an $x\in X$ such that $x\rightarrow r_{1}\in M$ then
other than the v-structures of $M_{1}$ and $M_{2}$, $M$ also contains a
v-structure $r_{2}\rightarrow r_{1}\leftarrow x$. In this case, $M$ obeys eq.
16.

Suppose $r_{1}\rightarrow r_{2}\in M$. Since
$M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$, we can partition the set of neighbors
of $r_{2}$ in $G_{2}$ into $Y$ and $Y^{\prime}$ such that $Y=\\{y:y-r_{2}\in
M_{2}\\}$ is a set of $j$ nodes, and
$Y^{\prime}=\\{y^{\prime}:r_{2}\rightarrow y^{\prime}\in M_{2}\\}$ of
$\delta_{2}-j$ nodes. From Lemma 2.7, for $y^{\prime}\in Y^{\prime}$,
$r_{2}\rightarrow y^{\prime}\in M$. Since $r_{1}\rightarrow r_{2}\in M$, from
item 1 of Theorem 3.1, for $y\in Y$, either $r_{2}\rightarrow y\in M$ or
$y\rightarrow r_{2}\in M$, otherwise, $r_{1}\rightarrow r_{2}-y$ is an induced
subgraph in $M$, contradicting item 1 of Theorem 3.1. If for two distinct
$y_{1},y_{2}\in Y$, $y_{1}\rightarrow r_{2},y_{2}\rightarrow r_{2}\in M$, then
we get a v-structure $y_{1}\rightarrow r_{2}\leftarrow y_{2}$ in $M$ such the
nodes of the v-structure are in $V_{G_{2}}$, but the v-structure is not in
$M_{2}$, implying $\mathcal{V}(M[V_{G_{2}}])\neq\mathcal{V}(M_{2})$, which
further implies $\mathcal{P}(M,V_{G_{2}})\neq M_{2}$, a contradiction. This
implies that there exists at most one $y\in Y$ such that $y\rightarrow
r_{2}\in M$. If there is no $y\in Y$ such that $y\rightarrow r_{2}\in M$ then
there won’t be any v-structure in $M$ with endpoints $r_{1}$ and $r_{2}$, and
in this case, $M$ contains only the v-structures of $M_{1}$ and $M_{2}$, as in
eq. 15. If there exists a $y\in Y$ such that $y\rightarrow r_{2}\in M$ then
other than the v-structures of $M_{1}$ and $M_{2}$, $M$ also contains a
v-structure $r_{1}\rightarrow r_{2}\leftarrow y$. In this case, $M$ obeys eq.
17.

This implies in all the possibilities, $M$ either follows eq. 15 or it follows
eq. 16 or it follows eq. 17. This completes the proof of item 1. ∎

As discussed in the introduction, there cannot be two distinct MECs with the
same skeleton and the same set of v-structures. Uniqueness of the MECs present
in items 2, 3 and 4 of Lemma 5.9 comes from this fact. We now prove items 2, 3
and 4 of Lemma 5.9.

###### Proof of item 2 of Lemma 5.9.

We construct an MEC of $G$ that obeys item 2 of Lemma 5.9. Let $M=M_{1}\cup
M_{2}\cup\\{r_{1}-r_{2}\\}$. To prove that $M$ obeys item 2, we have to show
the following: (a) $M$ is an MEC of $G$, (b) $M$ obeys eq. 15, (c)
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$, and (d)
$M\in\text{MEC}(G,r_{1},0,i+1)$.

We first show that $M$ is an MEC of $G$. From the construction of $M$, it is
clear that the skeleton of $M$ is $G$. Thus, the only thing we have to show is
that $M$ is an MEC, i.e., it obeys items 1 and 2 of Theorem 3.1.

We start with proving item 1 of Theorem 3.1. Suppose $M$ contains an induced
subgraph of the form $a\rightarrow b-c$. Since
$M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$, there cannot be an edge of the form
$x\rightarrow r_{1}$ in $M_{1}$. Similarly, since
$M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$, there cannot be an edge of the form
$y\rightarrow r_{2}\in M_{2}$. Since $M=M_{1}\cup M_{2}\cup\\{r_{1}-r_{2}\\}$,
there cannot be an edge of the form $x\rightarrow r_{1}$ and $y\rightarrow
r_{2}$ in $M$. This implies either (a) $a,b,c\in V_{G_{1}}$, or (b) $a,b,c\in
V_{G_{2}}$. If $a,b,c\in V_{G_{1}}$ then from the construction of $M$,
$a\rightarrow b-c\in M_{1}$. Since $M_{1}$ is an MEC of a tree graph $T_{1}$,
this contradicts item 1 of Theorem 3.1. This implies that this case cannot
occur. Similarly, there cannot be $a,b,c\in V_{G_{2}}$. This implies $M$
cannot have any induced subgraph of the form $a\rightarrow b-c$.

We now show that each directed edge $u\rightarrow v$ of $M$ obeys item 2 of
Theorem 3.1. Let $u\rightarrow v$ be a directed edge in $M$. From the
construction of $M$, either $u\rightarrow v\in M_{1}$, or $u\rightarrow v\in
M_{2}$. Since $M_{1}$ is an MEC of a tree graph $G_{1}$, if $u\rightarrow v\in
M_{1}$ then from item 2 of Theorem 3.1, $u\rightarrow v$ is part of an induced
subgraph of $M_{1}$ of the form either $w\rightarrow u\rightarrow v$ or
$w\rightarrow v\leftarrow u$. From the construction of $M$, the induced
subgraph of $M_{1}$ is an induced subgraph of $M$. Thus, when $u\rightarrow
v\in M_{1}$, $u\rightarrow v$ obeys item 2 of Theorem 3.1 for $M$. Similarly,
if $u\rightarrow v\in M_{2}$ then $u\rightarrow v$ obeys item 2 of Theorem 3.1
for $M$. This shows that $M$ obeys item 2 of Theorem 3.1.

The above discussion implies that $M$ obeys items 1 and 2 of Theorem 3.1. This
further implies that $M$ is an MEC.

We now show that the v-structures of $M$ obey eq. 15. From the construction of
$M$, $M_{1}$ and $M_{2}$ are the induced subgraphs of $M$ on $V_{G_{1}}$ and
$V_{G_{2}}$. Therefore, $\mathcal{V}(M[V_{G_{1}}])=\mathcal{V}(M_{1})$, and
$\mathcal{V}(M[V_{G_{2}}])=\mathcal{V}(M_{2})$. Since $r_{1}-r_{2}\in M$,
other than the v-structures of $M_{1}$ and $M_{2}$, $M$ cannot have any
v-structures. This shows that the v-structures in $M$ obey eq. 15.

We now show that $\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$. From the
construction of $M$, $M[V_{G_{1}}]=M_{1}$, and $M[V_{G_{2}}]=M_{2}$. This
implies $\mathcal{V}(M[V_{G_{1}}])=\mathcal{V}(M_{1})$, and
$\mathcal{V}(M[V_{G_{2}}])=\mathcal{V}(M_{2})$. From Definition 2.5, this
further implies $\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$.

From the construction of $M$, $M_{1}$ is an induced subgraph of $M$. In
$M_{1}$, $i$ edges adjacent to $r_{1}$ are undirected and the remaining
$\delta_{1}-i$ adjacent edges of $r_{1}$ in $M_{1}$ are directed outward of
$r_{1}$. Since $M_{1}$ is an induced subgraph of $M$, the $i$ adjacent
undirected edges of $M_{1}$ are undirected in $M$ as well. Other than that, it
has an additional undirected edge $r_{1}-r_{2}$, adjacent to $r_{1}$. This
implies the total number of undirected edges adjacent to $r_{1}$ in $M$ is
$i+1$. Therefore, no edge adjacent to $r_{1}$ in $M$ is incoming to $r_{1}$,
and $i+1$ undirected edges adjacent to $M$ are undirected. This implies
$M\in\text{MEC}(G,r_{1},0,i+1)$. This completes the proof of item 2 of Lemma
5.9.

∎

###### Proof of item 3 of Lemma 5.9.

We construct an MEC of $G$ using the following steps:

  1. 1.

Initialize $M=M_{1}\cup M_{2}\cup\\{r_{2}\rightarrow r_{1}\\}$.

  2. 2.

Pick an edge $x-r_{1}\in M_{1}$. Replace the edge $x-r_{1}$ in $M$ with
$x\rightarrow r_{1}$.

  3. 3.

Update $M$ by replacing $u-v$ of $M$ with $u\rightarrow v$, if $u-v\in M_{1}$
and there exists an undirected path from $r_{1}$ to $(u,v)$ in $M_{1}$ such
that the path does not contain $x$.

We show that $M$ constructed using the above steps will obey item 3 of Lemma
5.9. To prove this, we have to show the following: (a) $M$ is an MEC of $G$,
(b) $M$ obeys eq. 16, (c) $\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$,
and (d) $M\in\text{MEC}(G,r_{1},1)$.

We first show that $M$ is an MEC i.e., it obeys items 1 and 2 of Theorem 3.1.

We start with showing that $M$ obeys item 1 of Theorem 3.1. Suppose $M$
contains an induced subgraph of the form $a\rightarrow b-c$. From the
construction of $M$, there are three possibilities: either (a) $a,b,c\in
V_{G_{1}}$, or (b) $a,b,c\in V_{G_{2}}$, or (c) $a=r_{2}$, $b=r_{1}$, and
$c\in V_{G_{1}}$. One by one, we show that none of the possibilities occurs.

Suppose $a,b,c\in V_{G_{1}}$. From the construction of $M$, $b-c\in M_{1}$
(note that items 2 and 3 do not change a directed edge in $M_{1}\cup
M_{2}\cup\\{r_{2}\rightarrow r_{1}\\}$ into an undirected edge), and either
$a\rightarrow b\in M_{1}$ or $a-b\in M_{1}$. If $a\rightarrow b\in M_{1}$ then
$a\rightarrow b-c$ is an induced subgraph in the MEC $M_{1}$, contradicting
item 1 of Theorem 3.1. And, if $a-b\in M_{1}$ then it must have been directed
at either at item 2 (first case) or at item 3 (second case). If it has been
directed at item 2 then $a=x,b=r_{1}$ and $c\neq x$ is a neighbor of $r_{1}$.
This implies $r_{1}-c$ is a path from $r_{1}$ to $(r_{1},c)$. But, then at
item 3, $r_{1}-c$ has been converted into $r_{1}\rightarrow c$. This implies
that the first case cannot occur. We now move to the second case. Suppose
$a-b$ has been directed at item 3. This implies there exists a path from
$r_{1}$ to $(a,b)$ in $M_{1}$. This further implies that there exists a path
from $r_{1}$ to $(b,c)$ in $M_{1}$. But, then, we have $b\rightarrow c\in M$
at item 3. This implies that there cannot be an induced subgraph $a\rightarrow
b-c$ in $M$ with $a,b,c\in V_{G_{1}}$.

Suppose $a,b,c\in V_{G_{2}}$. From the construction of $M$, an induced
subgraph of $M$ with vertices in $V_{G_{2}}$ is also an induced subgraph of
$M_{2}$ (note that items 2 and 3 does not make any change in an edge with the
endpoints in $V_{G_{2}}$). Since $M_{2}$ is an MEC of a tree graph $G_{2}$,
from item 1 of Theorem 3.1, there cannot be an induced subgraph $u\rightarrow
v-w\in M_{2}$. This shows that there cannot be an induced subgraph
$a\rightarrow b-c$ in $M$ with $a,b,c\in V_{G_{2}}$.

Suppose $a=r_{2}$, $b=r_{1}$, and $c\in V_{G_{1}}$. From the construction of
$M$, this implies $r_{1}-c\in M_{1}$. There are two cases, either $c=x$, or
$c\neq x$. If $c=x$, then at item 2, we have $c\rightarrow b\in M$. Therefore,
this case cannot occur. Suppose $c\neq x$. But, edge $r_{1}-c$ is a path from
$r_{1}$ to $(r_{1},c)$. Then, it must have been directed at item 3. This
implies that this possibility also cannot occur. This shows that $M$ cannot
have an induced subgraph of the form $u\rightarrow v-w$. This implies that $M$
obeys item 1 of Theorem 3.1.

We now show that $M$ obeys item 2 of Theorem 3.1. Suppose $u\rightarrow v$ is
a directed edge in $M$ then either $u,v\in V_{G_{1}}$, or $u,v\in V_{G_{2}}$,
or $u=r_{2}$ and $v=r_{1}$. We show that in each of the possibilities
$u\rightarrow v$ in $M$ obeys item 2 of Theorem 3.1.

Suppose $u,v\in V_{G_{1}}$. From the construction of $M$, a directed edge of
$M_{1}$ is a directed edge in $M$. Therefore, since $u\rightarrow v\in M$,
either $u\rightarrow v\in M_{1}$ or $u-v\in M_{1}$. Suppose $u\rightarrow v\in
M_{1}$. Since $M_{1}$ is an MEC of a tree graph $G_{1}$, from item 2 of
Theorem 3.1, $u\rightarrow v$ is part of an induced subgraph of $M_{1}$ of the
form either $u\rightarrow v\leftarrow w$ or $w\rightarrow u\rightarrow v$.
Since from the construction of $M$, a directed induced subgraph of $M_{1}$ is
an induced subgraph of $M$. Therefore, $u\rightarrow v$ in $M$ obeys item 2 of
Theorem 3.1.

When $u-v\in M_{1}$ then it must have been directed in $M$ either at item 2 or
at item 3. Suppose $u-v\in M_{1}$ and it gets directed in $M$ at item 2. Then,
$u=x$ and $v=r_{2}$. In that case, $u\rightarrow v$ is part of an induced
subgraph $r_{2}\rightarrow r_{1}\leftarrow x$, obeying item 2 of Theorem 3.1.
Suppose $u-v\in M_{1}$ and it gets directed in $M$ at item 3. This implies
there exists an undirected path from $r_{2}$ to $(u,v)$ in $M_{1}$, and the
path does not contain $x$. Let the path be
$P=(x_{0}=r_{1},x_{1},\ldots,x_{l-1}=u,x_{l}=v)$ for some $l\geq 1$. From the
construction of $M$, for $0\leq i<l$, $x_{i}\rightarrow x_{i+1}\in M$ because
$P_{i}=(x_{0}=r_{1},\ldots,x_{i},x_{i+1})$ is an undirected path in $M_{1}$
from $r_{1}$ to $(x_{i},x_{i+1})$, and $P_{i}$ does not contain $x$ either. If
$l>1$ then $u\rightarrow v$ is part of an induced subgraph $x_{l-2}\rightarrow
x_{l-1}\rightarrow x_{l}$ in $M$. And, if $l=1$ then $r_{1}=u$, and
$u\rightarrow v$ is part of an induced subgraph $r_{2}\rightarrow
r_{1}\rightarrow v$ in $M$. Thus, we show that if $u,v\in V_{G_{1}}$ then
$u\rightarrow v$ obeys item 2 of Theorem 3.1.

Suppose $u,v\in V_{G_{2}}$. From the construction of $M$, $M_{2}$ is an
induced subgraph of $M$. This implies $u\rightarrow v\in M_{2}$. Since $M_{2}$
is an MEC of a tree graph $G_{2}$, from item 2 of Theorem 3.1, $u\rightarrow
v$ is part of an induced subgraph of $M_{2}$ of the form either $u\rightarrow
v\leftarrow w$ or $w\rightarrow u\rightarrow v$. Since from the construction
of $M$, an induced subgraph of $M_{2}$ is an induced subgraph of $M$.
Therefore, $u\rightarrow v$ in $M$ obeys item 2 of Theorem 3.1.

We now show that $r_{2}\rightarrow r_{1}$ in $M$ also obeys item 2 of Theorem
3.1. $r_{2}\rightarrow r_{1}$ is part of an induced subgraph $r_{2}\rightarrow
r_{1}\leftarrow x$ in $M$. Thus, we show that each edge of $M$ obeys item 2 of
Theorem 3.1.

The above discussion shows that $M$ is an MEC as it obeys items 1 and 2 of
Theorem 3.1. From the construction of $M$, the skelton of $M$ is $G$. This
implies $M$ is an MEC of $G$.

We now show that $M$ obeys eq. 16. From the construction of $M$, directed
edges of $M_{1}$ and $M_{2}$ are directed edges of $M$. Also,
$r_{2}\rightarrow r_{1}\leftarrow x$ is a v-structure in $M$. This implies
$\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\\{r_{2}\rightarrow
r_{1}\leftarrow x\\}\subseteq\mathcal{V}(M)$. For the completeness of the
proof, we show that if $u\rightarrow v\leftarrow w$ is a v-structure in $M$
then either it is a v-structure of $M_{1}$ or it is a v-structure of $M_{2}$,
or $u=r_{2}$, $v=r_{1}$ and $w=x$, i.e.,
$\mathcal{V}(M)\subseteq\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\\{r_{2}\rightarrow
r_{1}\leftarrow x\\}$. This further implies
$\mathcal{V}(M)=\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\\{r_{2}\rightarrow
r_{1}\leftarrow x\\}$, i.e., $M$ obeys eq. 16.

Suppose there exists a v-structure $u\rightarrow v\leftarrow w$ in $M$. From
the construction of $M$, there are following possibilities: (a) $u,v,w\in
V_{G_{1}}$, or (b) $u=r_{2}$, $v=r_{1}$, and $w$ is a neighbor of $r_{1}$ in
$V_{G_{1}}$, or (c) $u,v,w\in V_{G_{2}}$.

Suppose $u,v,w\in V_{G_{1}}$. From the construction of $M$, if $a\rightarrow
b\in M_{1}$ then $a\rightarrow b\in M$. This implies either $u-v\in M_{1}$ or
$u\rightarrow v\in M_{1}$, and either $v-w\in M_{1}$ or $v\leftarrow w\in
M_{1}$. From item 1 of Theorem 3.1, either $u\rightarrow v\leftarrow w\in
M_{1}$ or $u-v-w\in M_{1}$ (recall that $M_{1}$ is an MEC of a tree graph
$G_{1}$). If $u\rightarrow v\leftarrow w\in M_{1}$ then the v-structure is a
v-structure of $M_{1}$. Suppose $u-v-w\in M_{1}$. Then, if $u\rightarrow v\in
M$ then it must have been directed either at item 2 or at item 2. Suppose
$u\rightarrow v\in M$ at item 2. Then, $u=x$ and $v=r_{1}$. But, then $v-w$ is
a path from $r_{1}$ to $(v,w)$ (and the path does not contain $x$). And, we
have $v\rightarrow w\in M$ at item 3, a contradiction, as the v-structure
implies $w\rightarrow v\in M$. This implies that this case cannot occur.
Suppose $u\rightarrow v\in M$ at item 3. Then, there exists a path from
$r_{1}$ to $(u,v)$, and the path does not contain $x$. Since $u-v-w\in M_{1}$,
the existence of a path from $r_{1}$ to $(u,v)$ in $M_{1}$ implies the
existence of a path from $r_{1}$ to $(v,w)$ in $M_{1}$, and the new path also
does not contain $x$. Also, since $M_{1}$ is an MEC of a tree graph $G_{1}$,
there cannot be two different paths from $r_{1}$ to $w$. This implies at item
2, if we have $u\rightarrow v\in M$ then we also have $v\rightarrow w\in M$.
But, this is a contradiction, as we have assumed that $u\rightarrow
v\leftarrow w\in M$. This implies there cannot be $u-v-w\in M_{1}$ and
$u\rightarrow v\leftarrow w\in M$.

Suppose $u=r_{2}$, $v=r_{1}$, and $w$ is a neighbor of $r_{1}$ in $V_{G_{1}}$.
Since $M_{1}\in\text{MEC}(G_{1},r_{1},0)$, either $r_{1}\rightarrow w\in
M_{1}$ or $r_{1}-w\in M_{1}$. From the construction of $M$, if
$r_{1}\rightarrow w\in M_{1}$ then $r_{1}\rightarrow w\in M$. But, we have
$r_{1}\leftarrow w\in M$. This implies that $r_{1}-w\in M_{1}$. From items 2
and 3, if we have $w\rightarrow r_{1}\in M$ then $w=x$, otherwise, we have
$r_{1}\rightarrow w\in M$ at item 3 as $r_{1}-w$ is an undirected path from
$r_{1}$ to $(r_{1},w)$, and the path does not contain $x$. This implies
$u=r_{2}$, $v=r_{1}$, and $w=x$.

We now move to the final possibility. Suppose $u,v,w\in V_{G_{2}}$. From the
construction of $M$, $M_{2}$ is an induced subgraph of $M$. This implies that
if $u,v,w\in V_{G_{2}}$ then $u\rightarrow v\leftarrow w$ is a v-structure in
$M_{2}$. Thus, we show that in all the possible scenarios, if $u\rightarrow
v\leftarrow w$ is a v-structure in $M$ then it is a v-structure either in
$M_{2}$ or in $M_{1}$, or $v=r_{1}$ and $\\{u,w\\}=\\{r_{2},x\\}$. This
completes the proof that $M$ obeys eq. 16.

The above discussion implies that
$\mathcal{V}(M[V_{G_{1}}])=\mathcal{V}(M_{1})$ and
$\mathcal{V}(M[V_{G_{2}}])=\mathcal{V}(M_{2})$. Therefore, from Definition
2.5, $\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$.

Since there is an incoming edge $r_{2}\rightarrow r_{1}$ in $M$,
$M\in\text{MEC}(G,r_{1},1)$. This completes the proof of item 3 of Lemma 5.9.
∎

###### Proof of item 4 of Lemma 5.9.

We construct an MEC of $G$ using the following steps:

  1. 1.

Initialize $M=M_{1}\cup M_{2}\cup\\{r_{1}\rightarrow r_{2}\\}$.

  2. 2.

Pick an edge $y-r_{2}\in M_{2}$. Replace the edge $y-r_{2}$ in $M$ with
$y\rightarrow r_{2}$.

  3. 3.

Update $M$ by replacing $u-v$ of $M$ with $u\rightarrow v$, if $u-v\in M_{2}$
and there exists an undirected path from $r_{2}$ to $(u,v)$ in $M_{2}$ such
that the path does not contain $y$.

We show that $M$ constructed using the above steps will obey item 4 of Lemma
5.9. To prove this, we have to show the following: (a) $M$ is an MEC of $G$,
(b) $M$ obeys eq. 17, (c) $\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$,
and (d) $M\in\text{MEC}(G,r_{1},0,i)$.

We first show that $M$ is an MEC i.e., it obeys items 1 and 2 of Theorem 3.1.

We start with proving that $M$ obeys item 1 of Theorem 3.1. Suppose $M$
contains an induced subgraph of the form $a\rightarrow b-c$. From the
construction of $M$, there are three possibilities: either (a) $a,b,c\in
V_{G_{1}}$, or (b) $a,b,c\in V_{G_{2}}$, or (c) $a=r_{1}$, $b=r_{2}$, and
$c\in V_{G_{2}}$. One by one, we show that none of the possibilities occurs.

Suppose $a,b,c\in V_{G_{1}}$. From the construction of $M$, an induced
subgraph of $M$ with vertices in $V_{G_{1}}$ is also an induced subgraph of
$M_{1}$ (note that items 2 and 3 does not make any change in an edge with the
endpoints in $V_{G_{1}}$). Since $M_{1}$ is an MEC of a tree graph $G_{1}$,
from item 1 of Theorem 3.1, there cannot be an induced subgraph $a\rightarrow
b-c\in M_{1}$. This implies that the first possibility cannot occur.

Suppose $a,b,c\in V_{G_{2}}$. From the construction of $M$, $b-c\in M_{2}$
(note that items 2 and 3 do not change a directed edge in $M_{1}\cup
M_{2}\cup\\{r_{1}\rightarrow r_{2}\\}$ into an undirected edge), and either
$a\rightarrow b\in M_{2}$ or $a-b\in M_{2}$. If $a\rightarrow b\in M_{2}$ then
$a\rightarrow b-c$ is an induced subgraph in the MEC $M_{2}$, contradicting
item 1 of Theorem 3.1. And, if $a-b\in M_{2}$ then it must have been directed
at either at item 2 (first case) or at item 3 (second case). If it has
directed at item 2 then $a=y,b=r_{2}$ and $c\neq y$ is a neighbor of $r_{2}$.
This implies $r_{2}-c$ is a path from $r_{2}$ to $(r_{2},c)$. But, then at
item 3, $r_{2}-c$ has been converted into $r_{2}\rightarrow c$. This implies
that the first case cannot occur. We move to the second case when $a-b$ has
been directed at item 3. This implies there exists a path from $r_{2}$ to
$(a,b)$ in $M_{2}$. This further implies that there exists a path from $r_{2}$
to $(b,c)$ in $M_{2}$. But, then, we have $b\rightarrow c\in M$ at item 3.
This shows that the second case also cannot occur. This further implies the
second possibility also cannot occur. We now move to the third possibility.

Suppose $a=r_{1}$, $b=r_{2}$, and $c\in V_{G_{2}}$. From the construction of
$M$, this implies $r_{2}-c\in M_{2}$. There are two cases, either $c=y$, or
$c\neq y$. If $c=y$, then at item 2, we have $c\rightarrow b\in M$. Therefore,
this case cannot occur. Suppose $c\neq y$. But, edge $r_{2}-c$ is a path from
$r_{2}$ to $(r_{2},c)$. Then, it must have been directed at item 3. This
implies that the third possibility also cannot occur. This shows that $M$
cannot have an induced subgraph of the form $u\rightarrow v-w$. This implies
that $M$ obeys item 1 of Theorem 3.1.

We now show that $M$ obeys item 2 of Theorem 3.1. Suppose $u\rightarrow v$ is
a directed edge in $M$ then either $u,v\in V_{G_{1}}$, or $u,v\in V_{G_{2}}$,
or $u=r_{1}$ and $v=r_{2}$. We show that in each of the possibilities
$u\rightarrow v$ in $M$ obeys item 2 of Theorem 3.1.

Suppose $u,v\in V_{G_{1}}$, then from the construction of $M$, $u\rightarrow
v\in M_{1}$. Since $M_{1}$ is an MEC of a tree graph $G_{1}$, from item 2 of
Theorem 3.1, $u\rightarrow v$ is part of an induced subgraph of $M_{1}$ of the
form either $u\rightarrow v\leftarrow w$ or $w\rightarrow u\rightarrow v$.
Since from the construction of $M$, an induced subgraph of $M_{1}$ is an
induced subgraph of $M$. Therefore, $u\rightarrow v$ in $M$ obeys item 2 of
Theorem 3.1.

Suppose $u,v\in V_{G_{2}}$. From the construction of $M$, either $u\rightarrow
v\in M_{2}$ or $u-v\in M_{2}$. Suppose $u\rightarrow v\in M_{2}$. Since
$M_{2}$ is an MEC of a tree graph $G_{2}$, from item 2 of Theorem 3.1,
$u\rightarrow v$ is part of an induced subgraph of $M_{2}$ of the form either
$u\rightarrow v\leftarrow w$ or $w\rightarrow u\rightarrow v$. From the
construction of $M$, a directed induced subgraph of $M_{2}$ is an induced
subgraph of $M$ (as a directed edge of $M_{2}$ is a directed edge of $M$, and
the skeletons of $M_{2}$ and $M[V_{G_{2}}]$ are the same). Therefore, in this
case also $u\rightarrow v$ in $M$ obeys item 2 of Theorem 3.1.

Suppose $u-v\in M_{2}$. Then, it must have been directed in $M$ either at item
2 or at item 3. Suppose $u-v\in M_{2}$ and it gets directed in $M$ at item 2.
Then, $u=y$ and $v=r_{2}$. In that case, $u\rightarrow v$ is part of an
induced subgraph $r_{1}\rightarrow r_{2}\leftarrow y$, obeying item 2 of
Theorem 3.1. Suppose $u-v$ gets directed in $M$ at item 3. This implies there
exists an undirected path from $r_{2}$ to $(u,v)$ in $M_{2}$, and the path
does not contain $y$. Let the path be
$P=(x_{0}=r_{2},x_{1},\ldots,x_{l-1}=u,x_{l}=v)$ for some $l\geq 1$. From the
construction of $M$, for $0\leq i<l$, $x_{i}\rightarrow x_{i+1}\in M$ because
$P_{i}=(x_{0}=r_{2},\ldots,x_{i},x_{i+1})$ is an undirected path in $M_{2}$
from $r_{2}$ to $(x_{i},x_{i+1})$, and $P_{i}$ does not contain $y$ either. If
$l>1$ then $u\rightarrow v$ is part of an induced subgraph $x_{l-2}\rightarrow
x_{l-1}\rightarrow x_{l}$ in $M$. And, if $l=1$ then $r_{2}=u$, and
$u\rightarrow v$ is part of an induced subgraph $r_{1}\rightarrow
r_{2}\rightarrow v$ in $M$. Thus, we show that if $u,v\in V_{G_{2}}$ then
$u\rightarrow v$ obeys item 2 of Theorem 3.1.

We now show that $r_{1}\rightarrow r_{2}$ in $M$ also obeys item 2 of Theorem
3.1. $r_{1}\rightarrow r_{2}$ is part of an induced subgraph $r_{1}\rightarrow
r_{2}\leftarrow y$ in $M$. Thus, we show that each edge of $M$ obeys item 2 of
Theorem 3.1.

The above discussion shows that $M$ is an MEC as it obeys items 1 and 2 of
Theorem 3.1. From the construction of $M$, the skelton of $M$ is $G$. This
implies $M$ is an MEC of $G$.

We now show that $M$ obeys eq. 17. From the construction of $M$, directed
edges of $M_{1}$ and $M_{2}$ are directed edges of $M$. Also,
$r_{1}\rightarrow r_{2}\leftarrow y$ is a v-structure in $M$. This implies
$\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\\{r_{1}\rightarrow
r_{2}\leftarrow y\\}\subseteq\mathcal{V}(M)$. For the completeness of the
proof, we show that if $u\rightarrow v\leftarrow w$ is a v-structure in $M$
then either it is a v-structure of $M_{1}$ or it is a v-structure of $M_{2}$,
or $u=r_{1},v=r_{2}$ and $w=y$, i.e.,
$\mathcal{V}(M)\subseteq\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\\{r_{1}\rightarrow
r_{2}\leftarrow y\\}$. This further implies
$\mathcal{V}(M)=\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\\{r_{1}\rightarrow
r_{2}\leftarrow y\\}$, i.e., $M$ obeys eq. 17.

Suppose there exists a v-structure $u\rightarrow v\leftarrow w$ in $M$. From
the construction of $M$, there are following possibilities: (a) $u,v,w\in
V_{G_{1}}$, or (b) $u=r_{1}$, $v=r_{2}$, and $w$ is a neighbor of $r_{2}$ in
$V_{G_{2}}$, or (c) $u,v,w\in V_{G_{2}}$. From the construction of $M$,
$M_{1}$ is an induced subgraph of $M$ (note that items 2 and 3 do not change
the orientation of any edge of $M_{1}$). This implies that if $u,v,w\in
V_{G_{1}}$ then $u\rightarrow v\leftarrow w$ is a v-structure in $M_{1}$.

Suppose $u=r_{1}$, $v=r_{2}$, and $w$ is a neighbor of $r_{2}$ in $V_{G_{2}}$.
Since $M_{2}\in\text{MEC}(G_{2},r_{2},0)$, either $r_{2}\rightarrow w\in
M_{2}$ or $r_{2}-w\in M_{2}$. From the construction of $M$ (items 1, 2 and 3),
if $r_{2}\rightarrow w\in M_{2}$ then $r_{2}\rightarrow w\in M$. But, we have
$r_{2}\leftarrow w\in M$. This implies that $r_{2}-w\in M_{2}$. From items 2
and 3, if we have $w\rightarrow r_{2}\in M$ then $w=y$, otherwise, we have
$r_{2}\rightarrow w\in M$ at item 3 as $r_{2}-w$ is an undirected path from
$r_{2}$ to $(r_{2},w)$, and the path does not contain $y$. This implies
$u=r_{1},v=r_{2}$, and $w=y$.

We now move to the final possibility. Suppose $u,v,w\in V_{G_{2}}$. From the
construction of $M$, if $a\rightarrow b\in M_{2}$ then $a\rightarrow b\in M$.
This implies either $u-v\in M_{2}$ or $u\rightarrow v\in M_{2}$, and either
$v-w\in M_{2}$ or $v\leftarrow w\in M_{2}$. From item 1 of Theorem 3.1, either
$u\rightarrow v\leftarrow w\in M_{2}$ or $u-v-w\in M_{2}$.

Suppose $u\rightarrow v\leftarrow w\in M_{2}$. Then, the v-structure is a
v-structure of $M_{2}$.

Suppose $u-v-w\in M_{2}$. Then, if $u\rightarrow v\in M$ then it must have
been directed either at item 2 or at item 2.

Suppose $u\rightarrow v$ is added to $M$ at item 2. Then, $u=y$ and $v=r_{2}$.
But, then $v-w$ is a path from $(r_{2})$ to $(v,w)$ (and the path does not
contain $y$). And, we have $v\rightarrow w\in M$ at item 3, a contradiction,
as the v-structure implies $w\rightarrow v\in M$. This implies that this case
cannot occur.

Suppose $u\rightarrow v$ is added to $M$ at item 3. Then, there exists a path
from $r_{2}$ to $(u,v)$, and the path does not contain $y$. Since $u-v-w\in
M_{2}$, the existence of a path from $r_{2}$ to $(u,v)$ in $M_{2}$ implies the
existence of a path from $r_{2}$ to $(v,w)$ in $M_{2}$, and the new path also
does not contain $y$. Also, since $M_{2}$ is an MEC of a tree graph $G_{2}$,
there cannot be two different paths from $r_{2}$ to $w$. This implies at item
3, if we have $u\rightarrow v\in M$ then we also have $v\rightarrow w\in M$.
But, this is a contradiction, as we have assumed that $u\rightarrow
v\leftarrow w\in M$. This implies there cannot be $u-v-w\in M_{2}$ and
$u\rightarrow v\leftarrow w\in M$. Thus, we show that in all the possible
scenarios, if $u\rightarrow v\leftarrow w$ is a v-structure in $M$ then it is
a v-structure either in $M_{1}$ or in $M_{2}$, or $u=r_{1},v=r_{2}$ and $w=y$.
This completes the proof that $M$ obeys eq. 17.

The above discussion implies that
$\mathcal{V}(M[V_{G_{1}}]=\mathcal{V}(M_{1})$ and
$\mathcal{V}(M[V_{G_{2}}]=\mathcal{V}(M_{2})$. Therefore, from Definition 2.5,
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$.

From the construction of $M$, $M_{1}$ is an induced subgraph of $M$. In
$M_{1}$, $i$ edges adjacent to $r_{1}$ are undirected and the remaining
$\delta_{1}-i$ adjacent edges of $r_{1}$ in $M_{1}$ are directed outward of
$r_{1}$. The only edge that is adjacent to $r_{1}$ in $M$ but not adjacent to
$r_{1}$ in $M_{1}$ is $r_{1}\rightarrow r_{2}$, which is directed outward of
$r_{1}$. Therefore, no edge adjacent to $r_{1}$ in $M$ is incoming to $r_{1}$,
and $i$ undirected edges adjacent to $M$ are undirected. This implies
$M\in\text{MEC}(G,r_{1},0,i)$.

This completes the proof of item 4 of Lemma 5.9. ∎

This completes the proof of Lemma 5.9. ∎

Lemma 5.7 implies the following corollary:

######  Corollary 5.10.

For $M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$, and
$M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$, the number of MECs $M$ of $G$ such that
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$ is $i+j+1$. More
specifically, $i$ MECs belong to $\text{MEC}(G,r_{1},1)$, and $j$ MECs belong
to $\text{MEC}(G,r_{1},0,i)$, and one MEC belongs to
$\text{MEC}(G,r_{1},0,i+1)$.

###### Proof.

From item 1 of Lemma 5.9, for any MEC $M$ of $G$, if
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$ then $M$ has to obey either
eqs. 15, 16 and 17. From item 2 of Lemma 5.9, there exists a unique MEC that
satisfies eq. 15, belonging to $\text{MEC}(G,r_{1},0,i+1)$.

Given $M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$, $i$ instances of $x$ exist such
that $x-r_{1}\in E_{M_{1}}$. According to item 3 of Lemma 5.9, for each
$x-r_{1}\in E_{M_{1}}$, there exists a unique MEC satisfying eq. 16.
Consequently, there are $i$ MECs following eq. 16, all belong to
$\text{MEC}(G,r_{1},1)$ as per item 3.

Given $M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$, $j$ instances of $y$ exist such
that $y-r_{2}\in E_{M_{2}}$. According to item 4 of Lemma 5.9, for each
$y-r_{2}\in E_{M_{2}}$, there exists a unique MEC satisfying eq. 17.
Consequently, there are $j$ MECs following eq. 17, all belong to
$\text{MEC}(G,r_{1},0,i)$ as per item 4.

Hence, the total count of MECs is $i+j+1$. Out of which, $i$ MECs belong to
$\text{MEC}(G,r_{1},1)$, and $j$ MECs belong to $\text{MEC}(G,r_{1},0,i)$, and
one MEC belongs to $\text{MEC}(G,r_{1},0,i+1)$. ∎

From Corollary 5.4, corresponding to each tuple $(M_{1},M_{2})$ such that
$M_{1}\in\text{MEC}(G_{1},r_{1},1)$ and $M_{2}\in\text{MEC}(G_{2},r_{2},1)$,
there are two MECs of $G$ that belong to $\text{MEC}(G,r_{1},1)$. From
Corollary 5.6, corresponding to each tuple $(M_{1},M_{2})$ such that
$M_{1}\in\text{MEC}(G_{1},r_{1},1)$ and $M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$,
there are $j+2$ MECs of $G$ that belong to $\text{MEC}(G,r_{1},1)$. From
Corollary 5.8, corresponding to each tuple $(M_{1},M_{2})$ such that
$M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$ and $M_{2}\in\text{MEC}(G_{2},r_{2},1)$,
there are $i+1$ MECs of $G$ that belong to $\text{MEC}(G,r_{1},1)$. From
Corollary 5.10, corresponding to each tuple $(M_{1},M_{2})$ such that
$M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$ and
$M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$, there are $i$ MECs of $G$ that belong
to $\text{MEC}(G,r_{1},1)$. This makes the total number of MECs of $G$ that
belongs to $\text{MEC}(G,r_{1},1)$ equal to as in item 1 of Lemma 3.2.

From Corollaries 5.4 and 5.6, corresponding to each tuple $(M_{1},M_{2})$ such
that $M_{1}\in\text{MEC}(G_{1},r_{1},1)$ and $M_{2}\in\text{MEC}(G_{2})$, no
MEC of $G$ belongs to $\text{MEC}(G,r_{1},0)$. From Corollary 5.8,
corresponding to each tuple $(M_{1},M_{2})$ such that
$M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$ and $M_{2}\in\text{MEC}(G_{2},r_{2},1)$,
there are one MEC of $G$ that belongs to $\text{MEC}(G,r_{1},0,i)$. From
Corollary 5.10, corresponding to each tuple $(M_{1},M_{2})$ such that
$M_{1}\in\text{MEC}(G_{1},r_{1},0,i)$ and
$M_{2}\in\text{MEC}(G_{2},r_{2},0,j)$, there are $j$ MECs of $G$ that belong
to $\text{MEC}(G,r_{1},0,i)$. From Corollary 5.10, for each tuple
$(M_{1},M_{2})$ such that $M_{1}\in\text{MEC}(G_{1},r_{1},0,i-1)$ and
$M_{2}\in\text{MEC}(G_{2},r_{2},0)$, there are one MEC of $G$ that belong to
$\text{MEC}(G,r_{1},0,i)$. This makes total number of MECs of $G$ that belongs
to $\text{MEC}(G,r_{1},0,i)$ equal to as in items 2 and 3 of Lemma 3.2.

This completes the proof of Lemma 3.2. ∎

###  5.2 Omitted proof of Section 3.2

We first go through some results of Sharma [2023]:

######  Definition 5.11 (Triangle Free Path, Sharma [2023]).

For a graph $G$, a path $P=(u_{1},u_{2},\ldots,u_{l})$ is said to be a
triangle-free path of $G$ if for any $1\leq i\leq l-2$, there does not exist
an edge between $u_{i}$ and $u_{i+2}$ in $G$, i.e., neither $u_{i}-u_{i+2}\in
E_{G}$ nor $u_{i}\rightarrow u_{i+2}\in E_{G}$ nor $u_{i}\leftarrow u_{i+2}\in
E_{G}$.

######  Lemma 5.12 (Sharma [2023]).

For an undirected chordal graph $G$, if $P$ is a triangle-free path of $G$
then $P$ is a chordless path of $G$.

######  Observation 5.13 (Observation 2.30 of Sharma [2023]).

Let $M$ be an MEC, and $P=(u_{1}=x,u_{2}=y,\ldots,u_{l-1}=u,u_{l}=v)$ be a
triangle-free path from $(x,y)$ to $(u,v)$ in $M$. If $u-v\in M$ then $P$ is
an undirected chordless path in $M$, more specifically $x-y\in M$.

######  Lemma 5.14 (Corollary 2.50 of Sharma [2023]).

Let $M$ be an MEC and $M^{\prime}$ be a projection of $M$. Let
$P=(u_{1},u_{2},\ldots,u_{l})$ be a triangle-free path in $M^{\prime}$. If
$u_{2}\rightarrow u_{1}\notin M$ then $P$ is also a triangle-free path in $M$.

######  Lemma 5.15 (Corollary 2.51 of Sharma [2023]).

Let $M$ be an MEC and $M^{\prime}$ be a projection of $M$. If
$P=(u_{1}=x,u_{2}=y,u_{3},\ldots,u_{l-1}=u,u_{l}=v)$ is a triangle-free path
from $(x,y)$ to $(u,v)$ in $M^{\prime}$, and $x\rightarrow y\in M$ then for
all $1\leq i<l$, $u_{i}\rightarrow u_{i+1}\in M$.

###### Proof of item 3 of Observation 3.6.

W.l.o.g., let us assume $i=1$. We start with the following observation.

######  Observation 5.16.

Let $P=(u_{0}=x,u_{1},\ldots,u_{l}=y)$ be a chordless path in $G_{1}$ from $x$
to $y$ such that $l\geq 2$, and $x,y\in r_{1}\cup N(r_{1},G_{1})$. Then, each
node of $P$ is in $r_{1}\cup N(r_{1},G_{1})$.

###### Proof.

There are two possibilities: either $x\in r_{1}$, or $x\notin r_{1}$.

  1. 1.

Suppose $x\in r_{1}$. Then, we claim that $y\in N(r_{1},G_{1})\setminus
r_{1}$.

Suppose $y\in r_{1}$. Then, since $r_{1}$ is a clique of $G_{1}$, $x-y\in
G_{1}$. But, this implies $P$ is not a chordless path in $G_{1}$, a
contradiction. This implies $y\notin r_{1}$. This further implies $y\in
N(r_{1},G_{1})\setminus r_{1}$.

Since $y\in N(r_{1},G_{1})\setminus r_{1}$, there must exist a node $z\in
r_{1}$ such that $y\in N(z,G_{1})$, i.e., $z-y\in G_{1}$. Since $r_{1}$ is a
clique in $G_{1}$, and $x,z\in r_{1}$, $x-z\in G_{1}$. This implies
$u_{0}-z,u_{l}-z\in G_{1}$. We claim that each node in $P$ is a neighbor of
$z$ in $G_{1}$.

Suppose there exists a node $u_{i}$ which is not a neighbor of $z$. Pick the
least such $i$. Since $u_{0}-z\in G_{1}$, $i>0$. Pick the least $j$ such that
$j>i$ and $u_{j}-z\in G_{1}$ (there must exist such $j$ as $u_{l}-z\in
G_{1}$). Then $(z,u_{i-1},u_{i},\ldots,u_{j},z)$ is a chordless cycle in
$G_{1}$ (since $P$ is a chordless path, there cannot be an edge between two
non-adjacent nodes $u_{a}$ and $u_{b}$ of $P$), a contradiction, as $G_{1}$ is
a chordal graph. This implies each node in $P$ is a neighbor of $z$ in
$G_{1}$. Since $z\in r_{1}$, this further implies each node of $P$ is in
$r_{1}\cup N(r_{1},G_{1})$.

  2. 2.

Suppose $x\notin r_{1}$. Since $x\in r_{1}\cup N(r_{1},G_{1})$ and $x\notin
r_{1}$, $x\in N(r_{1},G_{1})\setminus r_{1}$. Then, there must exist a node
$z\in r_{1}$ such that $x\in N(z,G_{1})$, i.e., $u_{0}-z\in G_{1}$. There are
two possibilities: either $z-y\in G_{1}$ or $z-y\notin G_{1}$.

Suppose $z-y\in G_{1}$. This implies $u_{0}-z\in G_{1}$ and $u_{l}-z\in
G_{1}$. Then, similar to the previous case, each node of the chordless path
$P$ is in $r_{1}\cup N(r_{1},G_{1})$.

Suppose $z-y\notin G_{1}$. This implies $y\notin r_{1}$. Because, if $y\in
r_{1}$ then since $r_{1}$ is a clique of $G_{1}$, we have $z-y\in G_{1}$,
contradicting our assumption. Since $y\in r_{1}\cup N(r_{1},G_{1})$ and
$y\notin r_{1}$, $y\in N(r_{1},G_{1})\setminus r_{1}$. Then, there must exist
a node $z^{\prime}\in r_{1}$ such that $y\in N(z^{\prime},G_{1})$. We show
that each node of the chordless path $P$ is either a neighbor of $z$ or a
neighbor of $z^{\prime}$.

Suppose there exists a node $u_{i}$ in $P$ which is not a neighbor of $z$ in
$G_{1}$, i.e., $u_{i}-z\notin G_{1}$. Pick the least such $i$. $i>0$ as
$u_{0}-z\in G_{1}$. This implies $u_{i-1}-z\in G_{1}$. We claim that for any
$j\geq i$, $z-u_{j}\notin G_{1}$. Suppose there exists a $j>i$ such that
$z-u_{j}\in G_{1}$ ($j\neq i$ as we have assumed $u_{i}-z\notin G_{1}$). Pick
the least $j$. Then $(z,u_{i-1},u_{i},\ldots,u_{j},z)$ is a chordless cycle in
$G_{1}$ (there cannot be an edge between two non-adjacent nodes $u_{a}$ and
$u_{b}$ of $P$, as $P$ is a chordless path), a contradiction, as $G_{1}$ is a
chordal graph. We further claim that for each $j\geq i-1$,
$z^{\prime}-u_{j}\in G_{1}$.

Suppose there exists $j\geq i-1$ such that $z^{\prime}-u_{j}\notin G_{1}$.
Pick the least such $j$. Now, pick the least $k>j$ such that
$z^{\prime}-u_{k}\in G_{1}$ (there must exist such $k$ because
$u_{l}-z^{\prime}\in G_{1}$). If $j=i-1$ then
$C=(z^{\prime},z,u_{i-1},u_{i},\ldots,u_{k},z^{\prime})$ is a chordless cycle
in $G_{1}$, and if $j>i-1$ then
$C=(z^{\prime},u_{j-1},u_{j},\ldots,u_{k},z^{\prime})$ is a chordless cycle in
$G_{1}$. Both give a contradiction, as $G_{1}$ is a chordal graph. This
implies that for each $j\geq i-1$, $z^{\prime}-u_{j}\in G_{1}$.

This further implies each node of $P$ is either a neighbor of $z$ or a
neighbor of $z^{\prime}$. Since both $z$ and $z^{\prime}$ are in $r_{1}$,
nodes of $P$ are in $r_{1}\cup N(r_{1},G_{1})$.

Therefore, in all the possibilities, nodes of $P$ are in $r_{1}\cup
N(r_{1},G_{1})$. This completes the proof of Observation 5.16. ∎

From item 3 of Lemma 3.7, for $u-v\in O_{1}$, if $u\rightarrow v\in O$ then
either (a) $u\rightarrow v$ is strongly protected in $O$ (item 3a of Lemma
3.7), or (b) there exists $x-y\in O_{1}$ such that $x\rightarrow y\in O$, and
there exists a triangle-free path from $(x,y)$ to $(u,v)$ in $M_{1}$ with
$(x,y)\neq(u,v)$ (item 3b of Lemma 3.7), or (c) there exists $x-y\in O_{1}$
such that $x\rightarrow y\in O$, and there exist triangle-free paths from
$(x,y)$ to $v$, and from $(v,u)$ to $x$ with $y\neq v$ and $u\neq x$ (item 3c
of Lemma 3.7). We show that (b) and (c) implies (a).

  1. 1.

Suppose $u-v\in O_{1}$ and $u\rightarrow v\in O$ because $u\rightarrow v$
obeys item 3b of Lemma 3.7, i.e., there exists $x-y\in O_{1}$ such that
$x\rightarrow y\in O$, and there exists a triangle-free path
$P=(a_{0}=x,a_{1}=y,\ldots,a_{l-1}=u,a_{l}=v)$ from $(x,y)$ to $(u,v)$ in
$M_{1}$ with $(x,y)\neq(u,v)$. Since $(x,y)\neq(u,v)$, $l\geq 2$. Also, since
$O_{1}$ is an induced subgraph of $M_{1}$, $u-v,x-y\in M_{1}$. From
Observation 5.13, $P$ is an undirected chordless path in $M_{1}$. Since the
skeleton of $M_{1}$ is $G_{1}$, $P$ is also a chordless path in $G_{1}$. Also,
since $u-v,x-y\in O_{1}$, $u,v,x,y\in V_{O_{1}}=r_{1}\cup N(r_{1},G_{1})$.
From Observation 5.16, all the nodes of $P$ is in $r_{1}\cup N(r_{1},G_{1})$.
Since $O$ is an induced subgraph of $M$, and $x\rightarrow y\in O$,
$x\rightarrow y\in M$. Since $M_{1}$ is a projection of $M$, and $P$ is a
triangle-free path in $M_{1}$ from $(x,y)$ to $(u,v)$ such that $x\rightarrow
y\in M$, from Lemma 5.15, for $0\leq i<l$, $a_{i}\rightarrow a_{i+1}\in M$.
This further implies $a_{l-2}\rightarrow a_{l-1}\rightarrow a_{l}$ is an
induced subgraph of $M$ (as the skeletons of $M[V_{G_{1}}]$ and $M_{1}$ are
the same). Since nodes of $P$ are in $r_{1}\cup N(r_{1},G_{1})\subseteq
V_{O}$, and $O$ is an induced subgraph of $M$, $a_{l-2}\rightarrow
a_{l-1}\rightarrow a_{l}$ is an induced subgraph of $O$. This implies
$u\rightarrow v$ is strongly protected in $O$, as it is part of the induced
subgraph $a_{l-2}\rightarrow a_{l-1}\rightarrow a_{l}\in O$, as shown in fig.
1.a (recall that $a_{l-1}=u$ and $a_{l}=v$).

  2. 2.

Suppose $u-v\in O_{1}$ and $u\rightarrow v\in O$ because $u\rightarrow v$
obeys item 3c of Lemma 3.7, i.e., there exists $x-y\in O_{1}$ such that
$x\rightarrow y\in O$, and there exist triangle-free paths
$P_{1}=(a_{0}=x,a_{1}=y,\ldots,a_{l}=v)$ from $(x,y)$ to $v$ in $M_{1}$ with
$y\neq v$, and $P_{2}=(b_{0}=v,b_{1}=u,\ldots,b_{m}=x)$ from $(v,u)$ to $x$
with $u\neq x$. Since $y\neq v$ and $u\neq x$, $l,m\geq 2$. Both $P_{1}$ and
$P_{2}$ must be undirected paths in $M_{1}$, otherwise, concatenation of
$P_{1}$ and $P_{2}$ will give a directed cycle in $M_{1}$, contradicting item
1 of Theorem 2.2. This implies nodes of $P_{1}$ and $P_{2}$ belong to the same
undirected connected component $\mathcal{C}$ of $M_{1}$. From item 2 of
Theorem 2.2, $\mathcal{C}$ is chordal. This implies $P_{1}$ and $P_{2}$ are
triangle-free path in $\mathcal{C}$. From Lemma 5.12, $P_{1}$ and $P_{2}$ are
chordless paths in $\mathcal{C}$, and in $M_{1}$, as $\mathcal{C}$ is an
undirected connected component of $M_{1}$. Since the skeleton of $M_{1}$ is
the skeleton of $G_{1}$, $P_{1}$ and $P_{2}$ are chordless paths in $G_{1}$.
Also, since $u-v,x-y\in O_{1}$, $u,v,x,y\in V_{O_{1}}=r_{1}\cup
N(r_{1},G_{1})$. From Observation 5.16, all the nodes of $P_{1}$ and $P_{2}$
belong to $r_{1}\cup N(r_{1},G_{1})$. Since $P_{1}$ and $P_{2}$ are chordless
paths in $M_{1}$, and $O_{1}=M_{1}[r_{1}\cup N(r_{1},G_{1})]$, $P_{1}$ and
$P_{2}$ are chordless paths in $O_{1}$.

We claim that $u-a_{l-1}\in O_{1}$. We first show that $u-a_{l-1}\in G_{1}$.
Suppose $u-a_{l-1}\notin G_{1}$, Then, we claim that for all $i\leq l-1$,
$u-a_{i}\notin G_{1}$. Suppose for some $j<l-1$, $u-a_{j}\in G_{1}$. Pick the
highest such $j$. Then, $C=(u,a_{j},a_{j+1},\ldots,a_{l-1},a_{l}=v,u)$ is a
chordless cycle in $G_{1}$, a contradiction, as $G_{1}$ is a chordal graph.
Then, we claim that
$C=(b_{m}=a_{0},a_{1},\ldots,a_{l}=b_{0},b_{1},\ldots,b_{m})$ is a chordless
cycle. Suppose $C$ is not a chordless cycle in $G_{1}$. Then, since $P_{1}$
and $P_{2}$ is a chordless path in $G_{1}$, there must exist $i$ and $j$ such
that $0<i<l$, $0<j<m$ and $a_{i}-b_{j}\in G_{1}$. Pick the highest such $i$
for which there exists a $j$ such that $0<j<m$ and $a_{i}-b_{j}\in G_{1}$.
Then, pick the smallest such $j$. As shown earlier, for all $i\leq l-1$,
$u-a_{i}\notin G_{1}$. Therefore $j>1$ (remember $u=b_{1}$). But, then
$C=(a_{i},a_{i+1},\ldots,a_{l}=b_{0},b_{1},\ldots,b_{j},a_{i})$ is a chordless
cycle in $G_{1}$. In any way, we get a chordless cycle in $G_{1}$, a
contradiction, as $G_{1}$ is a chordal graph. This implies $u-a_{l-1}\in
G_{1}$.

Since $u,a_{l-1}$ are in the same undirected connected component of $M_{1}$
(an MEC of $G_{1}$), and $u-a_{l-1}\in G_{1}$ (the skeleton of $M_{1}$),
$u-a_{l-1}\in M_{1}$ (edge between two nodes of the same undirected connected
component of an MEC must be undirected, otherwise, it will create a directed
cycle and violate item 1 of Theorem 2.2). Since $O_{1}$ is an induced subgraph
of $M_{1}$, and $u,a_{l-1}\in V_{O_{1}}$ (as shown earlier), $u-a_{l-1}\in
O_{1}$.

We now prove that $u\rightarrow v$ is strongly protected in $O$. We first show
that for each $0\leq i<l$, $a_{i}\rightarrow a_{i+1}\in O$. Since $O$ is the
projection of $M$, and $u\rightarrow v,x\rightarrow y\in O$, $u\rightarrow
v,x\rightarrow y\in M$. Since $M_{1}$ is a projection of $M$, and $P_{1}$ is a
triangle-free path in $M_{1}$ from $(x,y)$ to $v$ such that $x\rightarrow y\in
M$, from Lemma 5.15, for $0\leq i<l$, $a_{i}\rightarrow a_{i+1}\in M$. Since
nodes of $P_{1}$ belong to $r_{1}\cup N(r_{1},G_{1})\subseteq V_{O}$, and $O$
is an induced subgraph of $M$, for $0\leq i<l$, $a_{i}\rightarrow a_{i+1}\in
O$.

Since from the construction, the skeletons of $O[V_{O_{1}}]$ and $O_{1}$ are
the same, either $u\rightarrow a_{l-1}\in O$, or $u-a_{l-1}\in O$, or
$u\leftarrow a_{l-1}\in O$. We show that in each possibility, $u\rightarrow v$
is strongly protected in $O$. If $u\rightarrow a_{l-1}\in O$ then
$u\rightarrow v$ is strongly protected in $O$ as it is part of an induced
subgraph $u\rightarrow a_{l-1}\rightarrow v\leftarrow u$, as shown in fig.
1.c. We now show that in other possibilities also $u\rightarrow v$ is strongly
protected.

Suppose either $u-a_{l-1}\in O$ or $u\leftarrow a_{l-1}\in O$. We claim that
$b_{2}\rightarrow b_{1}\in O$. Suppose $b_{2}\rightarrow b_{1}\notin O$. Since
$P_{2}$ is a triangle-free path in $M_{1}$, the subpath
$P_{2}^{\prime}=(b_{2}=u,b_{3},\ldots,b_{m})$ of $P$ is a triangle-free path
in $M_{1}$. If $b_{2}\rightarrow b_{1}\notin M$ then from Lemma 5.14,
$P_{2}^{\prime}$ is a triangle-free path in $M$. As discussed earlier, each
edge of the triangle-free path $P_{1}$ is directed in $O$. This implies a
subpath of $P$, $P_{1}^{\prime}=(a_{0},a_{1},\ldots,a_{l-1})$, is a directed
triangle-free path in $O$. Also, from our assumption, either $a_{l-1}-b_{2}\in
O$ or $a_{l-1}\rightarrow b_{2}\in O$. Since $O$ is an induced subgraph of
$M$, concatenaiton of $P_{1}^{\prime}$, $a_{l-1}-b_{2}$ (or
$a_{l-1}\rightarrow b_{2}$), and $P_{2}^{\prime}$ makes a directed cycle in
$M$, contradicting item 1 of Theorem 2.2. This implies if $u-a_{l-1}\in O$ or
$u\leftarrow a_{l-1}\in O$ then $b_{2}\rightarrow b_{1}\in O$. But, then,
$u\rightarrow v$ is strongly protected in $O$ due to part of an induced
subgraph of the form $b_{2}\rightarrow(b_{1}=u)\rightarrow(b_{0}=v)$.

Thus, we show that for chordal graph $G$, items 3b and 3c of Lemma 3.7 imply
item 3a of Lemma 3.7. This completes the proof item 3 of Observation 3.6. ∎

###### Proof of Observation 3.15.

We start with the following claim and observations:

######  Claim 5.17.

For $i\in\\{1,2\\}$, for any three nodes $u$, $v$, and $w$ belonging to an
undirected connected component $\mathcal{C}$ of $M_{i}$, there does not exist
a directed cycle $(u,v,w,u)$ in $M$.

######  Observation 5.18.

For $i\in\\{1,2\\}$, if $u\rightarrow v\in M_{i}$ then $u\rightarrow v\in M$.

###### Proof.

W.l.o.g., let us assume $a=1$. Suppose $u\rightarrow v\in M_{1}$. From
Definition 2.13, at step 1 of the construction of $M$, $u\rightarrow v\in M$.
At step 2, we replace an undirected edge with a directed one. This implies
once an edge is directed in $M$ at step 1, it remains directed in $M$. This
implies $u\rightarrow v\in M$. This completes the proof of Observation 5.18. ∎

######  Corollary 5.19.

For $i\in\\{1,2\\}$, $u,v\in V_{G_{i}}$, if $u\rightarrow v\in M$ then either
$u-v\in M_{i}$ or $u\rightarrow v\in M_{i}$.

###### Proof.

W.l.o.g., let us assume $a=1$. Suppose $u,v\in V_{G_{1}}$ and $u\rightarrow
v\in M$. From the construction of $M$,
$\textup{skeleton}({M[V_{G_{1}}]})=\textup{skeleton}({M_{1}})$. This implies
either $u-v\in M_{1}$, or $u\rightarrow v\in M_{1}$, or $v\rightarrow u\in
M_{1}$. But, if $v\rightarrow u\in M_{1}$ then from Observation 5.18,
$v\rightarrow u\in M$, a contradiction, as $u\rightarrow v\in M$. Thus, the
options that remain are $u-v\in M_{1}$ and $u\rightarrow v\in M_{1}$. This
completes the proof of Corollary 5.19. ∎

######  Corollary 5.20.

For $i\in\\{1,2\\}$, for $u,v\in V_{G_{i}}$, if $u-v\in M$ then $u-v\in
M_{i}$.

###### Proof.

W.l.o.g., let us assume $i=1$. Suppose $u,v\in V_{G_{1}}$ and $u-v\in M$. From
the construction of $M$,
$\textup{skeleton}({M[V_{G_{1}}]})=\textup{skeleton}({M_{1}})$. This implies
either $u-v\in M_{1}$, or $u\rightarrow v\in M_{1}$, or $v\rightarrow u\in
M_{1}$. But, if $u\rightarrow v\in M_{1}$ or $v\rightarrow u\in M_{1}$ then
from Observation 5.18, $u\rightarrow v\in M$ or $v\rightarrow u\in M$, a
contradiction, as $u-v\in M$. Thus, the option that remains is $u-v\in M_{1}$.
This completes the proof of Corollary 5.20. ∎

The above claim, observation, and corollaries imply the following:

######  Observation 5.21.

For $i\in\\{1,2\\}$, for any three nodes $u$, $v$, and $w$ belonging to
$V_{G_{i}}$, there does not exist a directed cycle $(u,v,w,u)$ in $M$.

###### Proof.

Contrary to Observation 5.21, suppose for some $i\in\\{1,2\\}$, there exist
nodes $u$, $v$, and $w$ belonging to $V_{G_{i}}$ such that $C=(u,v,w,u)$ is a
directed cycle in $M$. From Corollaries 5.19 and 5.20, $C$ is a cycle in
$M_{i}$. Since $M_{i}$ is an MEC, from item 1 of Theorem 2.2, none of the
edges of the cycle is directed in $M_{i}$. This implies all the node belongs
to the same undirected connected component of $M_{i}$. This contradicts Claim
5.17. This implies our assumption is wrong. This proves Observation 5.21. ∎

Observation 5.21 implies the following:

######  Observation 5.22.

There do not exist three nodes $u$, $v$, and $w$ in $M$ such that $(u,v,w,u)$
forms a directed cycle in $M$.

###### Proof.

Contrary to Observation 5.22, let us assume that there exist $u$, $v$, and $w$
in $M$ such that $(u,v,w,u)$ forms a directed cycle in $M$. We claim that
either all the nodes of the cycle belong to $V_{G_{1}}$ (i.e., $u,v,w\in
V_{G_{1}}$) or all the nodes belong to $V_{G_{2}}$ (i.e., $u,v,w\in
V_{G_{2}}$).

Suppose neither all the nodes of the cycle are in $V_{G_{1}}$ nor all the
nodes are in $V_{G_{2}}$. This implies there exists a node in the cycle that
belongs to $V_{G_{1}}\setminus V_{G_{2}}$ and another node in the cycle that
belongs to $V_{G_{2}}\setminus V_{G_{1}}$. However, from the construction,
there are no edges between $V_{G_{1}}\setminus V_{G_{2}}$ and
$V_{G_{2}}\setminus V_{G_{1}}$ in $G$ because $I=V_{G_{1}}\cap V_{G_{2}}$ is a
vertex separator that separates $V_{G_{1}}\setminus I$ and $V_{G_{2}}\setminus
I$ in $G$. According to Observation 3.12, $G$ is the skeleton of $M$. This
implies there cannot be an edge between nodes in $V_{G_{1}}\setminus
V_{G_{2}}$ and $V_{G_{2}}\setminus V_{G_{1}}$. But, in $M$, there exists an
edge between each pair of nodes in the cycle. This implies that the scenario
where a node of the cycle is in $V_{G_{1}}\setminus V_{G_{2}}$ and another in
$V_{G_{2}}\setminus V_{G_{1}}$ cannot occur. Therefore, all the nodes of the
cycle must either be in $V_{G_{1}}$ or in $V_{G_{2}}$.

From Observation 5.21, there cannot exist a directed cycle $(u,v,w,u)$ in $M$
such that all the nodes are either in $V_{G_{1}}$ or $V_{G_{2}}$. Hence, our
assumption is wrong. This completes the proof of Observation 5.22. ∎

We now demonstrate that Observation 5.22 implies the absence of any directed
cycle in $M$. Let’s assume the existence of a directed cycle in $M$. Select
the smallest-length directed cycle $C=(u_{0},u_{1},\ldots,u_{l}=u_{0})$ in
$M$. Our claim is that $l=2$.

Suppose $l>2$. As $G$ is the skeleton of $M$,
$C=(u_{0},u_{1},\ldots,u_{l},u_{l+1}=u_{0})$ forms a cycle in $G$. Since $G$
is chordal, an edge in $G$ must exist between two non-adjacent nodes $u_{i}$
and $u_{j}$ of $C$. Without loss of generality, let’s assume $i<j$. Then,
either $u_{i}-u_{j}\in M$ or $u_{i}\rightarrow u_{j}\in M$ or
$u_{j}\rightarrow u_{i}\in M$. Consequently, either
$(u_{0},u_{1},\ldots,u_{i},u_{j},u_{j+1},\ldots,u_{l},u_{l+1}=u_{0})$ or
$(u_{j},u_{i},u_{i+1},\ldots,u_{j})$ forms a directed cycle in $M$ with a
smaller length than cycle $C$. This contradicts our choice of picking the
smallest directed cycle. Thus, $l=2$.

From Observation 5.22, there cannot exist a directed cycle of length two in
$M$. Therefore, no directed cycle exists in $M$, indicating that $M$ is a
chain graph. This completes the proof of Observation 3.15. ∎

###### Proof of Claim 5.17.

The following two claims prove Claim 5.17.

######  Claim 5.23.

For $i\in\\{1,2\\}$, for any three nodes $u$, $v$, and $w$ belonging to an
undirected connected component $\mathcal{C}$ of $M_{i}$ such that
$V_{\mathcal{C}}\cap r_{i}=\varnothing$, there does not exist a directed cycle
$(u,v,w,u)$ in $M$.

######  Claim 5.24.

For $i\in\\{1,2\\}$, for any three nodes $u$, $v$, and $w$ belonging to an
undirected connected component $\mathcal{C}$ of $M_{i}$ such that
$V_{\mathcal{C}}\cap r_{i}\neq\varnothing$, there does not exist a directed
cycle $(u,v,w,u)$ in $M$.

For any $i\in\\{1,2\\}$, an undirected connected component of $M_{i}$ can be
of two types: either $V_{\mathcal{C}}\cap r_{i}=\varnothing$ or
$V_{\mathcal{C}}\cap r_{i}\neq\varnothing$. Claims 5.23 and 5.24 show that in
both of the possibilities, Claim 5.17 is valid. This completes the proof of
Claim 5.17. ∎

###### Proof of Claim 5.23.

Contrary to Claim 5.23, let us assume that for some $i\in\\{1,2\\}$, there
exists $u$, $v$, and $w$ belonging to an undirected connected component
$\mathcal{C}$ of $M_{i}$ such that $V_{\mathcal{C}}\cap r_{i}=\varnothing$,
and $(u,v,w,u)$ is a directed cycle in $M$. From the construction of $M$,
$\textup{skeleton}({M[V_{\mathcal{C}}]})=\mathcal{C}$. This implies
$u-v,v-w,w-c\in\mathcal{C}$. Before moving ahead, we go through the following
claim.

######  Claim 5.25.

For $i\in\\{1,2\\}$, let $\mathcal{C}$ be an undirected connected component of
$M_{i}$ such that $V_{\mathcal{C}}\cap r_{i}=\varnothing$. Then, for
$u-v\in\mathcal{C}$, $u-v\in M$.

From Claim 5.25, $u-v,v-w,w-c\in M$. This implies $(u,v,w,u)$ is an undirected
cycle in $M$, contradicting our assumption. This implies that our assumption
is wrong. This completes the proof of Claim 5.23. ∎

###### Proof of Claim 5.25.

Contrary to Claim 5.25, let us assume that for some $i\in\\{1,2\\}$, there
exists an undirected connected component $\mathcal{C}$ of $M_{i}$ such that
$V_{\mathcal{C}}\cap r_{i}=\varnothing$, and there exists $u-v\in\mathcal{C}$
such that $u\rightarrow v\in M$. W.l.o.g., let us assume $i=1$.

Before moving ahead, we go through the following observation:

######  Observation 5.26.

For $i\in\\{1,2\\}$, let $\mathcal{C}$ be an undirected connected component of
$M_{i}$, and $u-v$ be an edge of $\mathcal{C}$ such that $u\rightarrow v\in
M$. Then, $u\rightarrow v$ has been added to $M$ either at step 1 of the
construction of $M$, or at step 2 of the construction of $M$ when
$\mathcal{C}$ has been considered.

From Observation 5.26, if $u\rightarrow v$ has been added to $M$ then it must
have been added either at step 1 of the construction of $M$, or at step 2 of
the construction of $M$, when $\mathcal{C}$ has been considered. Since
$V_{\mathcal{C}}\cap r_{1}=\varnothing$, $\mathcal{C}$ has not been considered
at step 2 of the construction of $M$. This implies $u\rightarrow v$ has been
added to $M$ at step 1 of the construction of $M$. This implies $u\rightarrow
v\in U_{M}(M_{1},M_{2},O)$.

Since $\mathcal{C}$ is an undirected connected component of $M_{1}$, each edge
of $\mathcal{C}$ is an undirected edge of $M_{1}$. This implies $u-v\in
M_{1}$. Since $u\rightarrow v\in U_{M}(M_{1},M_{2},O)$, the following
observation implies $u\rightarrow v\in O$.

######  Observation 5.27.

If $u-v\in M_{1}$ and $u\rightarrow v\in U_{M}(M_{1},M_{2},O)$ (i.e.,
$u\rightarrow v$ added to $M$ at step 1 of the construction of $M$) then
$u\rightarrow v\in O$.

From Observation 5.27, $u\rightarrow v\in O$. This further implies that for
$u-v\in\mathcal{C}$ if $u\rightarrow v\in M$ then $u\rightarrow v\in
O[V_{\mathcal{C}}\cap V_{O}]$, contradicting Observation 5.28.

######  Observation 5.28.

Let $\mathcal{C}$ be an undirected connected component of $M_{1}$ such that
$r_{1}\cap V_{\mathcal{C}}=\varnothing$. Then, $O[V_{\mathcal{C}}\cap V_{O}]$
is an undirected graph.

This implies our assumption was wrong that $u\rightarrow v\in M$. This
completes the proof of Claim 5.25. ∎

###### Proof of Observation 5.26.

W.l.o.g., let us assume $i=1$. If $u\rightarrow v$ has been added to $M$ at
step 1 of the construction of $M$ then we are done. Suppose $u\rightarrow v$
has not been added to $M$ at step 1 of the construction of $M$. Then, it must
have added to $M$ at step 2 when some undirected connected component
$\mathcal{C}^{\prime}$ of $M_{1}$ or $M_{2}$ is considered. We show at step 2
of the construction of $M$, when any other undirected connected component is
considered, $u\rightarrow v$ has not been added to $M$.

Since two different undirected connected component of an MEC does not share
any vertices, for any other undirected connected component
$\mathcal{C}^{\prime}$ of $M_{1}$, $V_{\mathcal{C}^{\prime}}\cap
V_{\mathcal{C}}=\varnothing$. This implies $u-v\notin\mathcal{C}^{\prime}$ and
$u\rightarrow v$ has not been added to $M$ at step 2 when
$\mathcal{C}^{\prime}$ has been considered.

For any undirected connected component $\mathcal{C}^{\prime}$ of $M_{2}$,
$V_{\mathcal{C}^{\prime}}\cap V_{\mathcal{C}}\subseteq r_{1}\cap
r_{2}\subseteq r_{2}\cup N(r_{2},G)$. This implies if
$u-v\in\mathcal{C}^{\prime}$ then $u,v\in r_{2}\cup N(r_{2},G_{2})$. But, at
step 2 of the construction of $M$, when $\mathcal{C}^{\prime}$ has been
considered, we can added $u\rightarrow v$ to $M$ only if $v\notin r_{2}\cup
N(r_{2},G_{2})$. This implies $u\rightarrow v$ has not been added to $M$ at
step 2 of the construction of $M$, when $\mathcal{C}^{\prime}$ has been
considered.

The above discussion implies that for $u-v\in\mathcal{C}$, if $u\rightarrow v$
has been added to $M$ then it must have been added either at step 1 of the
construction of $M$ or at step 2 of the construction of $M$ when $\mathcal{C}$
has been considered. ∎

###### Proof of Observation 5.27.

From Definition 2.13, if $u-v\in M_{1}$ and $u\rightarrow v\in
U_{M}(M_{1},M_{2},O)$ then either $u\rightarrow v\in M_{2}$ or $u\rightarrow
v\in O$. $u\rightarrow v\in M_{2}$ implies that $u,v\in V_{M_{1}}\cap
V_{M_{2}}=I$. Since $O_{2}=M_{2}[V_{O_{2}}]$, for $u,v\in I$, $u\rightarrow
v\in M_{2}$ implies $u\rightarrow v\in O_{2}$, as from the construction,
$I\subseteq V_{O_{2}}$. Since $O\in\mathcal{E}(O_{1},O_{2})$, therefore, from
item 1 of Definition 3.8, we have $u\rightarrow v\in O$. Thus, we can say that
if $u-v\in M_{1}$ and $u\rightarrow v\in U_{M}(M_{1},M_{2},O)$ then
$u\rightarrow v\in O$. ∎

###### Proof of Observation 5.28.

Suppose $\mathcal{C}$ is an undirected connected component of $M_{1}$ such
that $r_{1}\cap V_{\mathcal{C}}=\varnothing$. Contrary to Observation 5.28,
let us assume that $O[V_{\mathcal{C}}\cap V_{O}]$ is not an undirected graph,
i.e., there exists a directed edge $u\rightarrow v\in O[V_{\mathcal{C}}\cap
V_{O}]$. Pick $u$ and $v$ using the following steps:

  1. 1.

Pick $u$ such that there is no incoming edge to $u$ in $O[V_{\mathcal{C}}\cap
V_{O}]$.

  2. 2.

Pick $v$ from the set $Y=\\{y:u\rightarrow y\in O[V_{\mathcal{C}}\cap
V_{O}]\\}$ such that for any $y\in Y$, $y\rightarrow v\notin O$.

The existence of such $u$ and $v$ is because $O$ is a chain graph. Since
$u\rightarrow v\in O[V_{\mathcal{C}}\cap V_{O}]$, $u\rightarrow v\in O$. From
item 3 of Definition 3.8, $u\rightarrow v$ must be strongly protected in $O$.
We now show that $u\rightarrow v$ is not strongly protected in $O$. This leads
to a contradiction, which further implies that $O[V_{\mathcal{C}}\cap V_{O}]$
is an undirected graph.

We go through the following claims and observations to prove $u\rightarrow v$
is not strongly protected in $O$.

######  Claim 5.29.

For any $x\in V_{\mathcal{C}}$, $x\rightarrow u\notin O$.

###### Proof of Claim 5.29.

Contrary to Claim 5.29, suppose there exists an $x\in V_{\mathcal{C}}$ such
that $x\rightarrow u\in O$. This implies $x\in V_{\mathcal{C}}\cap V_{O}$, and
$x\rightarrow u\in O[V_{\mathcal{C}}\cap V_{O}]$, contradicting our choice of
$u$ (recall that from the choice of $u$ (item 1), there is no incoming edge to
$u$ in $O[V_{\mathcal{C}}\cap V_{O}]$). This implies that our assumption is
wrong. This completes the proof of Claim 5.29. ∎

######  Observation 5.30.

Let $\mathcal{C}$ be an undirected connected component of $M_{1}$ such that
$V_{\mathcal{C}}\cap r_{1}=\varnothing$. Then, for any $x\in V_{\mathcal{C}}$,
$N(x,G)\subseteq V_{G_{1}}$.

###### Proof of Observation 5.30.

Suppose $\mathcal{C}$ is an undirected connected component of $M_{1}$ such
that $V_{\mathcal{C}}\cap r_{1}=\varnothing$, $x$ is a node in
$V_{\mathcal{C}}$, and $y$ is a neighbor of $x$ in $G$. We show that $y\in
V_{G_{1}}$.

Since $V_{\mathcal{C}}\cap r_{1}=\varnothing$, and $\mathcal{C}$ is an
undirected connected component of $M_{1}$, $x\in V_{G_{1}}\setminus r_{1}$.
Since $I=r_{1}\cap r_{2}$ is a vertex separator of $G$ that separates
$V_{G_{1}}\setminus I$ and $V_{G_{2}}\setminus I$, $x\in V_{G_{1}}\setminus
I$. This implies $y\notin V_{G_{2}}\setminus I$. Since $V_{G}$ is a disjoint
union of $V_{G_{1}}$ and $V_{G_{2}}\setminus I$, this further implies $y\in
V_{G_{1}}$. This implies $N(x,G)\subseteq V_{G_{1}}$. This completes the proof
of Observation 5.30. ∎

######  Observation 5.31.

Let $\mathcal{C}$ be an undirected connected component of $M_{1}$. For
$u-v\in\mathcal{C}$, if $x\rightarrow u\in M_{1}$ then $x\rightarrow v\in
M_{1}$.

###### Proof of Observation 5.31.

Suppose $\mathcal{C}$ is an undirected connected component of $M_{1}$, there
exists an undirected edge $u-v\in\mathcal{C}$, and there exists a directed
edge $x\rightarrow u\in M_{1}$. There are two possibilities: either $x-v\in
G_{1}$ or $x-v\notin G_{1}$ (remember $G_{1}$ is the skeleton of $M_{1}$). If
$x-v\notin G_{1}$ then $x\rightarrow u-v$ is an induced subgraph of $M_{1}$,
contradicting item 3 of Theorem 2.2. This implies $x-v\in G_{1}$. Then, there
must be $x\rightarrow v\in M_{1}$, otherwise, $(x,u,v,x)$ is a directed cycle
in $M$, contradicting item 1 of Theorem 2.2. This completes the proof of
Observation 5.31. ∎

######  Claim 5.32.

For any $x\notin V_{\mathcal{C}}$, $x\rightarrow u\in O$ if, and only if,
$x\rightarrow v\in O$.

###### Proof of Claim 5.32.

From Observation 5.30, the neighbors of $\mathcal{C}$ in $M$ is in
$V_{G_{1}}$. Since $u\in V_{\mathcal{C}}$, $v\in V_{G_{1}}$. For any $x\notin
V_{\mathcal{C}}$, from Corollary 5.19, if $x\rightarrow u\in M$ then
$x\rightarrow v\in M_{1}$ (if $x-u\in M_{1}$ then $x$ and $u$ are in the same
undirected connected component $\mathcal{C}$ of $M_{1}$). From Observation
5.31, for any $x\notin V_{\mathcal{C}}$, if $x\rightarrow u\in M_{1}$ then
$x\rightarrow v\in M_{1}$. From Observation 5.18, if $x\rightarrow v\in M_{1}$
then $x\rightarrow v\in M$. This implies that for $x\notin V_{\mathcal{C}}$,
if $x\rightarrow u\in M$ then $x\rightarrow v\in M$. Since $O$ is an induced
subgraph of $M$, and $v\in V_{O}$, for $x\notin V_{\mathcal{C}}$, if
$x\rightarrow u\in O$ then $x\rightarrow v\in O$. Similarly, we can show that
for $x\notin V_{\mathcal{C}}$, if $x\rightarrow v\in O$ then $x\rightarrow
u\in O$. This implies that for $x\notin V_{\mathcal{C}}$, $x\rightarrow u\in
O$ if, and only if, $x\rightarrow v\in O$. ∎

######  Claim 5.33.

$u\rightarrow v$ cannot be part of an induced subgraph $w\rightarrow
u\rightarrow v$ in $O$ (as shown in fig. 1.a).

###### Proof of Claim 5.33.

From Claim 5.29, if $w\in\mathcal{C}$ then $w\rightarrow u\notin O$. And, from
Claim 5.32, if $w\notin\mathcal{C}$ and $w\rightarrow u\in O$ then
$w\rightarrow v\in O$. This implies $w\rightarrow u\rightarrow v$ is not an
induced subgraph in $O$. This completes the proof of Claim 5.33. ∎

######  Claim 5.34.

$u\rightarrow v$ cannot be part of an induced subgraph $w\rightarrow
v\leftarrow u$ in $O$ (as shown in fig. 1.b).

###### Proof of Claim 5.34.

Suppose $u\rightarrow v$ is part of an induced subgraph $w\rightarrow
v\leftarrow u$ in $O$. Since $w\rightarrow v\in O$ and $w\rightarrow u\notin
O$, from Claim 5.32, $w\in\mathcal{C}$. This implies $u,v,w\in V_{M_{1}}$, as
$\mathcal{C}$ is an undirected connected component of $M_{1}$. Since
$u,v,w\in\mathcal{C}$, and from the construction,
$\textup{skeleton}({M[V_{G_{1}}]})=\textup{skeleton}({M_{1}})$, we have
$u-v-w$ is an induced subgraph in $M_{1}$. This further implies that $u-v-w$
is an induced subgraph in $O_{1}$ as $V_{O_{1}}=V_{M_{1}}\cap V_{O}$, and
$O_{1}$ is an induced subgraph of $M_{1}$. This contradicts item 2 of
Definition 3.8. This implies that our assumption is wrong. This completes the
proof of Claim 5.34. ∎

######  Claim 5.35.

$u\rightarrow v$ cannot be part of an induced subgraph $u\rightarrow
w\rightarrow v\leftarrow u$ in $O$ (as shown in fig. 1.c).

###### Proof of Claim 5.35.

Suppose $u\rightarrow v$ is part of an induced subgraph $u\rightarrow
w\rightarrow v\leftarrow u$ in $O$. Since $w\rightarrow v\in O$ and
$w\rightarrow u\notin O$, from Claim 5.32, $w\in\mathcal{C}$. This implies
$u,v,w\in V_{O}\cap V_{\mathcal{C}}$. From the choice of $u$ and $v$ that we
have (items 1 and 2) there cannot exist any $w$ such that $u\rightarrow
w\rightarrow v\leftarrow u\in O$. This implies that our assumption is wrong.
This completes the proof of Claim 5.35. ∎

######  Claim 5.36.

$u\rightarrow v$ cannot be part of an induced subgraph $u\rightarrow
v\leftarrow w-u-w^{\prime}\rightarrow v$ in $O$ (as shown in fig. 1.d).

###### Proof of Claim 5.36.

Suppose $u\rightarrow v$ is part of an induced subgraph $u\rightarrow
v\leftarrow w-u-w^{\prime}\rightarrow v$ in $O$. Since $w\rightarrow
v,w^{\prime}\rightarrow v\in O$ and $w\rightarrow u,w^{\prime}\rightarrow
u\notin O$, from Claim 5.32, $w,w^{\prime}\in\mathcal{C}$. This implies
$u,v,w,w^{\prime}\in V_{M_{1}}$, as $\mathcal{C}$ is an undirected connected
component of $M_{1}$. Since $w,v,w^{\prime}\in\mathcal{C}$, and from the
construction, $\textup{skeleton}({M[V_{G_{1}}]})=\textup{skeleton}({M_{1}})$,
we have $w-v-w^{\prime}$ is an induced subgraph in $M_{1}$. This further
implies that $w-v-w^{\prime}$ is an induced subgraph in $O_{1}$ as
$V_{O_{1}}=V_{M_{1}}\cap V_{O}$, and $O_{1}$ is an induced subgraph of
$M_{1}$. This contradicts item 2 of Definition 3.8. This implies that our
assumption is wrong. This completes the proof of Claim 5.36. ∎

Claims 5.33, 5.34, 5.35 and 5.36 imply that $u\rightarrow v$ is not strongly
protected in $O$, contradicting item 3 of Definition 3.8. This implies our
assumption that there exists a directed edge in $O[V_{\mathcal{C}}\cap V_{O}]$
is wrong. This further implies $O[V_{\mathcal{C}}\cap V_{O}]$ is an undirected
graph. This completes the proof of Observation 5.28. ∎

###### Proof of Claim 5.24.

Contrary to Claim 5.24, suppose for some $i\in\\{1,2\\}$, there exist nodes
$u$, $v$, and $w$ belonging to an undirected connected component $\mathcal{C}$
of $M_{i}$ such that $V_{\mathcal{C}}\cap r_{i}\neq\varnothing$, and
$(u,v,w,u)$ is a directed cycle in $M$. W.l.o.g., let us assume $i=1$.

######  Claim 5.37.

No node of the cycle belongs to $r_{1}$.

###### Proof.

If a node of the cycle belongs to $r_{1}$ then all the nodes of the cycle are
in $r_{1}\cup N(r_{1},G_{1})\subseteq V_{O}$. From Observation 3.13, $O$ is an
induced subgraph of $M$. This implies $O$ contains the directed cycle. But,
this is a contradiction as $O$ is a partial MEC (Definition 2.3), and a
partial MEC is a chain graph. This implies no node of the cycle belongs to
$r_{1}$. ∎

######  Claim 5.38.

At least one node of the cycle is not in $r_{1}\cup N(r_{1},G_{1})$.

###### Proof.

Contrary to Claim 5.38, suppose all the nodes of the cycle belong to
$r_{1}\cup N(r_{1},G_{1})$. Since $r_{1}\cup N(r_{1},G_{1})\subseteq V_{O}$.
From Observation 3.13, $O$ is an induced subgraph of $M$. This implies $O$
contains the directed cycle. But, this is a contradiction as $O$ is a partial
MEC (Definition 2.3), and a partial MEC is a chain graph. This implies our
assumption is incorrect. This validates Claim 5.38. ∎

Since $V_{\mathcal{C}}\cap r_{1}\neq\varnothing$, while running step 2 of the
construction of $M$, at some iteration, $\mathcal{C}$ gets considered at step
2 of the construction of $M$. Let $\tau$ be the LBFS ordering of $\mathcal{C}$
constructed at step 2a of the construction of $M$. Since $\tau$ starts with
$V_{\mathcal{C}}\cap r_{1}$ (from step 2a of the construction of $M$), the
following claims are intuitive:

######  Claim 5.39.

For two nodes $x,y\in\mathcal{C}$, if $x\in V_{\mathcal{C}}\cap r_{1}$ and
$y\notin V_{\mathcal{C}}\cap r_{1}$ then $\tau(x)<\tau(y)$.

######  Claim 5.40.

For two nodes $x,y\in\mathcal{C}$, if $x\in V_{\mathcal{C}}\cap(r_{1}\cup
N(r_{1},G_{1}))$ and $y\notin V_{\mathcal{C}}\cap(r_{1}\cup N(r_{1},G_{1}))$
then $\tau(x)<\tau(y)$.

The following claim comes from the implementation of step 2b of the
construction of $M$.

######  Claim 5.41.

For $u-v\in\mathcal{C}$, if $v\notin r_{1}\cup N(r_{1},G_{1})$, and
$\tau(u)<\tau(v)$ then $v\rightarrow u\notin M$.

###### Proof.

Contrary to Claim 5.41, suppose $v\rightarrow u\in M$. From Observation 5.26,
either $v\rightarrow u$ has been added to $M$ at step 1 of the construction of
$M$, or at step 2 of the construction of $M$ when $\mathcal{C}$ has been
considered.

If $v\rightarrow u$ is added to $M$ at step 1 of the construction of $M$ then
$v\rightarrow u\in U_{M}(M_{1},M_{2},O)$. From Observation 5.27, $v\rightarrow
u\in O$. This implies $v,u\in V_{M_{1}}\cap V_{O}=r_{1}\cup N(r_{1},G_{1})$.
But, this is a contradiction, as we have given $v\notin r_{1}\cup
N(r_{1},G_{1})$. This implies $v\rightarrow u$ is not added to $M$ at step 1
of the construction of $M$.

Since $\tau(u)<\tau(v)$, the precondition of step 2b implies $v\rightarrow u$
cannot be added to $M$ at step 2.

The above discussion implies $v\rightarrow u\notin M$. This completes the
proof of Claim 5.41. ∎

W.l.o.g., let us assume that $w$ has the highest rank in $\tau$ among the
nodes in the directed cycle $(u,v,w,u)$, i.e., $\tau(u)<\tau(w)$ and
$\tau(v)<\tau(w)$.

We first show that all the edges of the cycle $(u,v,w,u)$ are not directed in
$M$. All the edges of the cycle $(u,v,w,u)$ are directed in $M$ implies
$u\rightarrow v,v\rightarrow w,w\rightarrow u\in M$. Since $\tau(u)<\tau(w)$,
from Claim 5.41, $w\rightarrow u\notin M$. This implies all three edges of the
cycle are not directed in $M$.

We now show that no two edges of the cycle $(u,v,w,u)$ are directed. Since
$w\rightarrow v\notin M$ (discussed in the previous paragraph), if two edges
are directed then it must be $u\rightarrow v$ and $v\rightarrow w$. From
Observation 5.26, the two directed edges must have been added to $M$ either at
step 1 or at step 2 when $\mathcal{C}$ has been considered. Since $w$ is of
highest rank in $\tau$ among the nodes in the directed cycle, from Claims 5.38
and 5.40, $w\in V_{\mathcal{C}}\setminus{r_{1}\cup N(r_{1},G_{1})}$. This
implies that while running step 2b, $u\rightarrow w$ gets added to $M$ due to
the preconditions of step 2(b)ii get satisfied. This implies $(u,v,w,u)$ is
not a cycle in $M$, a contradiction. Therefore, no two edges of the cycle
$(u,v,w,u)$ are directed.

We now show that not even a single edge of cycle $(u,v,w,u)$ of $M$ is
directed. Since $w\rightarrow v\notin M$, if an edge of the cycle is directed
then there are two possibilities: either $u\rightarrow v\in M$ (that means
$u\rightarrow v-w-u$ is a directed cycle in $M$) or $v\rightarrow w\in M$
(that means $u-v\rightarrow w-u$ is a directed cycle in $M$). The following
claims show that both possibilities do not occur.

######  Claim 5.42.

There do not exist nodes $u,v,w\in\mathcal{C}$ such that $u\rightarrow
v-w-u\in M$, $w\notin r_{1}\cup N(r_{1},G_{1})$, and rank of $w$ in $\tau$ is
highest among the nodes in the cycle, where $\tau$ is the LBFS ordering of
$\mathcal{C}$ that we get at step 2a of the construction of $M$.

######  Claim 5.43.

There do not exist nodes $u,v,w\in\mathcal{C}$ such that $u-v\rightarrow
w-u\in M$, and rank of $w$ in $\tau$ is highest among the nodes in the cycle,
where $\tau$ is the LBFS ordering of $\mathcal{C}$ that we get at step 2a of
the construction of $M$.

Claims 5.42 and 5.43 imply that none of the edges of the cycle $(u,v,w,u)$ in
$M$ is directed. This achieves our goal of ensuring that $(u,v,u,v)$ does not
form a directed cycle in $M$. This completes the proof of Claim 5.24. ∎

###### Proof of Claim 5.42.

Suppose there exist nodes $u,v,w\in\mathcal{C}$ such that $u\rightarrow
v-w-u\in M$, $w\notin r_{1}\cup N(r_{1},G_{1})$, and rank of $w$ in $\tau$ is
highest among the nodes in the cycle, where $\tau$ is the LBFS ordering of
$\mathcal{C}$ that we get at step 2a of the construction of $M$. Let
$Y=\\{y:y\in V_{\mathcal{C}},\tau(y)<\tau(w)$, and $u\rightarrow y-w-u\in
M\\}$. We pick a $v\in Y$ such that for all $y\in Y$, $y\rightarrow v\notin
M$. We first show that such $v$ always exists.

Suppose there does not exist a $v\in Y$ such that for all $y\in Y$,
$y\rightarrow v\notin M$. Then, there exists a cycle
$C_{1}=(v_{1},v_{2},\ldots,v_{m},v_{m+1}=v_{1})$ in $M$ such that for $1\leq
i\leq m$, $v_{i}\in Y$, and $v_{i}\rightarrow v_{i+1}\in M$. Since nodes in
$Y$ are in $V_{\mathcal{C}}$, we pick the node $v_{j}$ among the nodes in the
cycle $C_{1}$ which has the highest rank in $\tau$. This implies
$\tau(v_{j})>\tau(v_{j+1})$. But, then, from Claim 5.41, $v_{j}\in r_{1}\cup
N(r_{1},G_{1})$, otherwise, we do not have $v_{j}\rightarrow v_{j+1}\in M$.
Since $v_{j}$ is the highest rank node among the nodes in $C_{1}$, from Claim
5.40, each node of the cycle is in $r_{1}\cup N(r_{1},G_{1})$. This implies
for $1\leq i\leq m$, $u_{i}-u_{i+1}\in\mathcal{C}$ does not get directed at
step 2 of the construction of $M$. Then, from Observations 5.26 and 5.27, for
$1\leq i\leq m$, $u_{i}\rightarrow u_{i+1}\in O$. This implies $O$ has a
directed cycle, a contradiction, as $O$ is a partial MEC (Definition 2.3).
This implies our assumption is not correct, and $v$ always exists.

The following claim provides us the potential induced subgraph of $M$ that
contains $u\rightarrow v$.

######  Claim 5.44.

For some $x\in V_{\mathcal{C}}$, $u\rightarrow v$ is part of an induced
subgraph $x\rightarrow u\rightarrow v$ of $M$, or $u\rightarrow v$ is part of
an induced subgraph $u\rightarrow x\rightarrow v\leftarrow u$ of $M$.

Claim 5.44 provides two possible induced subgraphs of $M$ that can contain
$u\rightarrow v$. We go through both of them.

  1. 1.

Suppose there exists $x\in V_{\mathcal{C}}$ such that $u\rightarrow v$ is part
of an induced subgraph $x\rightarrow u\rightarrow v$ of $M$. We first claim
that $\tau(x)<\tau(w)$.

Suppose $\tau(w)<\tau(x)$. Since $w\in V_{\mathcal{C}}\setminus{r_{1}\cap
N(r_{1},G_{1})}$, from Claim 5.40, $x\in V_{\mathcal{C}}\setminus{r_{1}\cap
N(r_{1},G_{1})}$. Also, since $\tau(u)<\tau(w)$, we have $\tau(u)<\tau(x)$.
But, then, from Claim 5.41, $x\rightarrow u\notin M$, a contradiction, as we
have assumed $x\rightarrow u\rightarrow v\in M$. This implies
$\tau(x)<\tau(w)$.

We now claim that $x-w\notin\mathcal{C}$. Suppose $x-w\in\mathcal{C}$. As
$\tau(x)<\tau(w)$, $\tau(v)<\tau(w)$, and $x-w,v-w\in\mathcal{C}$, from
Definition 2.10, $x-v\in\mathcal{C}$. From the construction of $M$,
$\textup{skeleton}({M[V_{\mathcal{C}}]})=\mathcal{C}$. This implies there is
an edge between $x$ and $v$ in $M$. This further implies $x\rightarrow
u\rightarrow v$ is not an induced subgraph of $M$, contradicting our
assumption. Therefore, $x-w\notin\mathcal{C}$.

As discussed above, $\tau(x)<\tau(w)$, $\tau(u)<\tau(w)$, and $x\rightarrow
u\in M$. This satisfies the precondition of step 2(b)i of the construction of
$M$ to make $u\rightarrow w\in M$. But, from our assumption $u-w\in M$, a
contradiction. This implies this possibility cannot occur.

  2. 2.

Suppose there exists $x\in V_{\mathcal{C}}$ such that $u\rightarrow v$ is part
of an induced subgraph $u\rightarrow x\rightarrow v\leftarrow u$ of $M$. We
first show that $x\in Y$ (Recall $Y=\\{y:y\in
V_{\mathcal{C}},\tau(y)<\tau(w)$, and $u\rightarrow y-w-u\in M\\}$). To prove
that $x\in Y$, we have to show that $\tau(x)<\tau(w)$, and $x-w\in M$.

Suppose $\tau(w)<\tau(x)$. Since $\tau(v)<\tau(w)$, we have $\tau(v)<\tau(x)$.
Also, since $w\notin V_{\mathcal{C}}\cap(r_{1}\cup N(r_{1},G_{1}))$, and
$\tau(w)<\tau(x)$, from Claim 5.40, $x\notin V_{\mathcal{C}}\cap(r_{1}\cup
N(r_{1},G_{1}))$. But, then, from Claim 5.41, $x\rightarrow v\notin M$,
contradicting our assumption that $u\rightarrow x\rightarrow v\leftarrow u\in
M$. This implies $\tau(x)<\tau(w)$.

Suppose $x-w\notin\textup{skeleton}({M})$. Then, $x\rightarrow v-w$ is an
induced subgraph of $M$ such that $\tau(x)<\tau(w)$, and $\tau(v)<\tau(w)$.
Then, from step 2(b)i of the construction of $M$, we have $v\rightarrow w\in
M$, a contradiction, as we have assumed $u\rightarrow v-w-u$ is a directed
cycle in $M$. This implies $x-w\in\textup{skeleton}({M})$. This implies either
$x\rightarrow w\in M$ or $w\rightarrow x\in M$ or $x-w\in M$. We show that the
first two possibility does not occur. If $x\rightarrow w\in M$ then we have a
directed cycle $(u,x,w,u)$ with two directed edges. But, we have shown earlier
that there cannot exist a directed cycle of length two with two directed
edges. This implies $x\rightarrow w\notin M$. Since $\tau(x)<\tau(w)$, and
$w\notin r_{1}\cup N(r_{1},G_{1})$, from Claim 5.41, $w\rightarrow x\notin M$.
Thus, the only option that remains is $x-w\in M$.

The above discussion implies that $x\in Y$. But, from the choice of $v$, there
cannot exist any $x\in Y$ such that $x\rightarrow v\in M$, a contradiction.
This implies our assumption is wrong, and there does not any $x\in
V_{\mathcal{C}}$ such that $u\rightarrow v$ is part of an induced subgraph
$u\rightarrow x\rightarrow v\leftarrow u$ in $M$.

The above discussion implies that $u\rightarrow v$ does not obey Claim 5.44, a
contradiction. This implies our assumption is wrong, and there do not exist
nodes $u,v,w\in\mathcal{C}$ such that $u\rightarrow v-w-u\in M$. This
completes the proof of Claim 5.42. ∎

###### Proof of Claim 5.43.

Suppose there exist $u,v,w\in\mathcal{C}$ such that $u-v\rightarrow w-u\in M$,
and rank of $w$ in $\tau$ is highest among the nodes in the cycle, where
$\tau$ is the LBFS ordering of $\mathcal{C}$ that we get at step 2a of the
construction of $M$. We pick $u,v,w$ with least $\tau(w)$, i.e., for any other
triplet $u^{\prime},v^{\prime},w^{\prime}\in\mathcal{C}$ such that
$u^{\prime}-v^{\prime}\rightarrow w^{\prime}-u^{\prime}\in M$, and rank of
$w^{\prime}$ in $\tau$ is highest among the nodes in the cycle
$(u^{\prime},v^{\prime},w^{\prime},u^{\prime})$ then
$\tau(w)<\tau(w^{\prime})$.

The following claim provides the potential induced subgraphs of $M$ that
contain $v\rightarrow w$.

######  Claim 5.45.

For some $x\in V_{\mathcal{C}}$ such that $\tau(x)<\tau(w)$, $v\rightarrow w$
is part of an induced subgraph $x\rightarrow v\rightarrow w$ or $v\rightarrow
x\rightarrow w\leftarrow v$ in $M$.

Claim 5.45 provides two possible induced subgraphs of $M$ that contains
$v\rightarrow w$. We go through both of them.

  1. 1.

Suppose there exists $x\in V_{\mathcal{C}}$ such that $\tau(x)<\tau(w)$, and
$v\rightarrow w$ is part of an induced subgraph $x\rightarrow v\rightarrow w$
of $M$. We claim that $x-u\in\mathcal{C}$.

Suppose $x-u\notin\mathcal{C}$. From Observation 5.26, $x\rightarrow v$ has
been added to $M$ either at step 1 of the construction of $M$, or at step 2 of
the construction of $M$ when $\mathcal{C}$ has been considered.

Suppose $x\rightarrow v$ has been added to $M$ at step 1 of the construction
of $M$. This implies $x\rightarrow v\in U_{M}(M_{1},M_{2},O)$. From
Observation 5.27, $x\rightarrow v\in O$. Now, if $u\in V_{O}$ then
$x\rightarrow v-u$ is an induced subgraph in $O$, contradicting $O$ as a
partial MEC (Definition 2.3). And, if $u\notin V_{O}$ then at step 2(b)i of
the construction of $M$ when $\mathcal{C}$ has been considered, we get
$v\rightarrow u\in M$, contradicting $(u,v,w,u)$ is a cycle. Thus, in each
case of this possibility, we get a contradiction. We move to the second
possibility.

Suppose $x\rightarrow v$ has been added to $M$ at step 2 of the construction
of $M$ when $\mathcal{C}$ has been considered. Then, from the preconditions of
steps 2b of the construction of $M$, we have $\tau(x)<\tau(v)$. Then,
$\tau(v)<\tau(u)$, otherwise, if $\tau(u)<\tau(v)$ then from Definition 2.10,
$x-u\in\mathcal{C}$, contradicting our assumption. But, if $\tau(v)<\tau(u)$,
then at step 2(b)i of the construction of $M$ when $\mathcal{C}$ has been
considered, we get $v\rightarrow u\in M$, contradicting $(u,v,w,u)$ is a
cycle.

Thus, in each case of both possibilities, we get a contradiction. This implies
$x-u\in\mathcal{C}$.

From the construction of $M$,
$\textup{skeleton}({M[V_{\mathcal{C}}]})=\mathcal{C}$. Therefore, we have
three possibilities: either $u\rightarrow x\in M$ or $x\rightarrow u\in M$ or
$x-u\in M$. We show that none of the possibilities occurs.

If $u\rightarrow x\in M$ then we get a directed cycle $(u,x,v,u)$ in $M$ with
two directed edges. We have shown earlier that $M$ does not have a directed
cycle of length three with two directed edges. This implies $u\rightarrow
x\notin M$.

Suppose $x\rightarrow u\in M$. Since $x\rightarrow v\rightarrow w$ is an
induced subgraph in $M$, $x-w\notin\textup{skeleton}({M})$. This implies
$x\rightarrow u-w$ is an induced subgraph in $M$ with $w\notin r_{1}\cup
N(r_{1},G)$, $\tau(x)<\tau(w)$, and $\tau(u)<\tau(w)$. This satisfies the
precondition of step 2(b)i of the construction of $M$ for adding $u\rightarrow
w$. And, therefore, while running step 2 of the construction of $M$ for the
undirected connected component $\mathcal{C}$, we add $u\rightarrow w$ at step
2(b)i. But, this creates a contradiction, as from our assumption $u-w\in M$
(as $u-v\rightarrow w-u$ is a cycle in $M$).

If $x-u\in M$ then we get a directed cycle $(x,v,u,x)$ in $M$ such that the
rank of all the three nodes of the cycle in $\tau$ is less than $\tau(w)$.
From Claim 5.38, one node of the cycle does not belong to $r_{1}\cup
N(r_{1},G_{1})$. From Claim 5.40, among the nodes of the cycle, the node with
the highest rank does not belong to $r_{1}\cup N(r_{1},G)$. From Claim 5.41,
$x$ cannot be the highest rank node. This implies either $u$ or $v$ is the
highest rank node. If $u$ is the highest rank node then $M$ contains a cycle
$x\rightarrow v-u-x$ such that the rank of all the three nodes of the cycle in
$\tau$ is less than $\tau(u)$. Claim 5.42 implies that such a cycle does not
exist. And, if $v$ is the highest rank node then we get a directed cycle
$u-x\rightarrow v-x$ in $M$ with the highest rank node is $\tau(v)$. Since
$\tau(v)<\tau(w)$, this contradicts our choice of $w$. This implies this case
also cannot occur.

The above discussion implies that in each case of this possibility, we get a
contradiction. This implies our assumption is wrong. We now move to the second
possibility of Claim 5.45.

  2. 2.

Suppose there exists $x\in V_{\mathcal{C}}$ such that $\tau(x)<\tau(w)$, and
$v\rightarrow w$ is part of an induced subgraph $v\rightarrow x\rightarrow
w\leftarrow v$ of $M$.

Given $\tau(x)<\tau(w)$, $\tau(u)<\tau(w)$, and $x-w,u-w\in\mathcal{C}$, from
Definition 2.10, $x-u\in\mathcal{C}$. From the construction of $M$,
$\textup{skeleton}({M[V_{\mathcal{C}}]})=\mathcal{C}$. Therefore, we have
three possibilities: either $u\rightarrow x\in M$ or $x\rightarrow u\in M$ or
$u-x\in M$. We show that none of the possibilities occurs.

Suppose $u\rightarrow x\in M$. Then, while running step 2 when $\mathcal{C}$
has been considered, we add $u\rightarrow w$ in $M$ as all the preconditions
of step item 2(b)ii is obeyed. But, this contradicts our assumption that
$(u,v,w,u)$ is a cycle in $M$. This implies $u\rightarrow x\notin M$.

Suppose $x\rightarrow u\in M$. Then, $M$ has a directed cycle $(v,x,u,v)$ with
two directed edges. As discussed earlier, there cannot exist a directed cycle
of length three with two directed edges. This implies $x\rightarrow u\notin
M$.

Suppose $u-x\in M$. Then, we get a directed cycle $(u,v,x,u)$ in $M$ such that
the rank of all the three nodes of the cycle in $\tau$ is less than $\tau(w)$.
From Claim 5.38, one node of the cycle does not belong to $r_{1}\cup
N(r_{1},G_{1})$. From Claim 5.40, among the nodes of the cycle, the node with
the highest rank does not belong to $r_{1}\cup N(r_{1},G)$. From Claim 5.41,
$u$ cannot be the highest rank node. This implies either $u$ or $x$ is the
highest rank node. If $u$ is the highest rank node then $M$ contains a cycle
$v\rightarrow x-u-v$ such that $u$ has the highest rank in $\tau$ among nodes
in the cycle. Claim 5.42 implies that such a cycle does not exist. And, if $x$
is the highest rank node then we get a directed cycle $u-v\rightarrow x-u$ in
$M$ with the highest rank node being $x$. Since $\tau(x)<\tau(w)$, this
contradicts our choice of $w$. This implies this cannot occur.

The above discussion implies $v\rightarrow w$ is part of none of the induced
subgraphs mentioned in Claim 5.45. This contradicts Claim 5.45. This implies
that our assumption is wrong. This validates Claim 5.43. ∎

###### Proof of Claim 5.44.

From Observation 5.26, $u\rightarrow v$ has been added to $M$ either at step 1
of the construction of $M$, or it has been added to $M$ at step 2 of the
construction of $M$, when $\mathcal{C}$ has been considered.

If $u\rightarrow v$ is added to $M$ at step 2 of the construction of $M$ then
$u\rightarrow v$ obeys Claim 5.44 (see step 2 of the construction of $M$).

Suppose $u\rightarrow v$ is added to $M$ at step 1 of the construction of $M$.
This implies $u\rightarrow v\in U_{M}(M_{1},M_{2},O)$. From Observation 5.27,
$u\rightarrow v\in O$. This implies $u,v\in V_{M_{1}}\cap
V_{O}=V_{O_{1}}=r_{1}\cup N(r_{1},G_{1})$. From Claim 5.37, $u,v\in
N(r_{1},G_{1})\setminus r_{1}$. Since $u,v\in N(r_{1},G_{1})\setminus r_{1}$,
and $I=r_{1}\cap r_{2}$ is a vertex separator of $G$ that separates
$V_{G_{1}}\setminus I$ and $V_{G_{2}}\setminus I$, neighbors of $u$ and $v$
belong to $V_{G_{1}}$. Since $u,v\in V_{O_{1}}$, and $O_{1}$ is an induced
subgraph of $M_{1}$, $u-v\in O_{1}$. From item 3 of Definition 3.8,
$u\rightarrow v$ is strongly protected in $O$. This implies $u\rightarrow v$
is part of one of the induced subgraphs of $O$ as shown in fig. 1.

  1. 1.

Suppose $u\rightarrow v$ is strongly protected in $O$ because it is part of an
induced subgraph $x\rightarrow u\rightarrow v$ of $O$ (as shown in fig. 1.a).
From Observation 3.13, $x\rightarrow u\in M$. As discussed earlier, the
neighbors of $u$ and $v$ are in $V_{G_{1}}$. This implies $x\in V_{G_{1}}$.
From Corollary 5.19, either $x-u\in M_{1}$ or $x\rightarrow u\in M$. From item
3 of Theorem 2.2, $x\rightarrow u-v$ cannot be an induced subgraph of $M$.
Therefore, $x-u\in M_{1}$. This implies $x\in\mathcal{C}$. This implies
$u\rightarrow v$ obeys Claim 5.44.

  2. 2.

Suppose $u\rightarrow v$ is strongly protected in $O$ because it is part of an
induced subgraph $x\rightarrow v\leftarrow u$ of $O$ (as shown in fig. 1.b).
From Observation 3.13, $x\rightarrow v\in M$. As discussed earlier, the
neighbors of $u$ and $v$ are in $V_{G_{1}}$. This implies $x\in V_{G_{1}}$.
From Corollary 5.19, either $x-v\in M_{1}$ or $x\rightarrow v\in M$. From item
3 of Theorem 2.2, $x\rightarrow u-v$ cannot be an induced subgraph of $M$.
Therefore, $x-u\in M_{1}$. Since $u,v,x\in V_{O}\cap V_{M_{1}}=V_{O_{1}}$, and
$\textup{skeleton}({O_{1}})=\textup{skeleton}({O[V_{O_{1}}]})$, $x-v-u$ is an
induced subgraph of $O_{1}$. This implies
$\mathcal{V}(O_{1})\neq\mathcal{V}(O[V_{O_{1}}])$ (as $x\rightarrow
v\leftarrow u\in O$ and $x-v-u\in O_{1}$). This contradicts item 2 of
Definition 3.8. This implies this case cannot occur.

  3. 3.

Suppose $u\rightarrow v$ is strongly protected in $O$ because it is part of an
induced subgraph $u\rightarrow x\rightarrow v\leftarrow u$ of $O$ (as shown in
fig. 1.c). From Observation 3.13, $u\rightarrow x\rightarrow v\leftarrow u\in
M$. As discussed earlier, the neighbors of $u$ and $v$ are in $V_{G_{1}}$.
This implies $x\in V_{G_{1}}$. From Corollary 5.19, (a) either $u-x\in M_{1}$
or $u\rightarrow x\in M$, and (b) either $x-v\in M_{1}$ or $x\rightarrow v\in
M_{1}$. If either $u\rightarrow x\in M_{1}$ or $x\rightarrow v\in M_{1}$ then
$(u,x,v,u)$ is a directed cycle in $M_{1}$, contradicting item 1 of Theorem
2.2. This implies $u-x,x-v\in M_{1}$, and $x\in\mathcal{C}$. This further
implies $u\rightarrow v$ obeys Claim 5.44.

  4. 4.

Suppose $u\rightarrow v$ is strongly protected in $O$ because it is part of an
induced subgraph $u-x\rightarrow v\leftarrow u-x^{\prime}\rightarrow v$ of $O$
(as shown in fig. 1.d). From Observation 3.13, $x\rightarrow v\in M$. As
discussed earlier, the neighbors of $u$ and $v$ are in $V_{G_{1}}$. This
implies $x\in V_{G_{1}}$. From Corollary 5.19, either $x-v\in M_{1}$ or
$x\rightarrow v\in M$. From Corollary 5.20, $u-x\in M_{1}$. If $x\rightarrow
v\in M_{1}$ then $(u,x,v,u)$ is a directed cycle in $M_{1}$, contradicting
item 1 of Theorem 2.2. This implies $x-v\in M_{1}$. Similarly,
$x^{\prime}-v\in M_{1}$. Since $u,v,x,x^{\prime}\in V_{O}\cap
V_{M_{1}}=V_{O_{1}}$, and
$\textup{skeleton}({O_{1}})=\textup{skeleton}({O[V_{O_{1}}]})$,
$x-v-x^{\prime}$ is an induced subgraph of $O_{1}$. This implies
$\mathcal{V}(O_{1})\neq\mathcal{V}(O[V_{O_{1}}])$ (as $x\rightarrow
v\leftarrow x^{\prime}\in O$ and $x-v-x^{\prime}\in O_{1}$). This contradicts
item 2 of Definition 3.8. This implies this case cannot occur.

The above discussion implies that $u\rightarrow v$ obeys Claim 5.44. This
completes the proof of Claim 5.44. ∎

###### Proof of Claim 5.45.

From Observation 5.26, either $v\rightarrow w$ has been added to $M$ at step 1
of the construction of $M$, or it has been added to $M$ at step 2 of the
construction of $M$ when $\mathcal{C}$ has been considered.

Suppose $v\rightarrow w$ has been added to $M$ at step 1 of the construction
of $M$. This implies $v\rightarrow w\in U_{M}(M_{1},M_{2},O)$. From
Observation 5.27, $v\rightarrow w\in O$. This implies $w\in V_{O}\cap
V_{M_{1}}=r_{1}\cup N(r_{1},G_{1})$, a contradiction, as we have assumed
$w\notin r_{1}\cup N(r_{1},G_{1})$. This implies $v\rightarrow w$ has not been
added to $M$ at step 1 of the construction of $M$.

If $v\rightarrow w$ is added to $M$ at step 2 of the construction of $M$ then
$v\rightarrow w$ obeys Claim 5.45 (see step 2 of the construction of $M$).

This implies $v\rightarrow w$ obeys Claim 5.45. This completes the proof of
Claim 5.45. ∎

###### Proof of Observation 3.16.

Suppose there exists an undirected connected component $\mathcal{C}$ of $M$
such that $\mathcal{C}$ is not chordal. Then, there must exist a chordless
cycle $C=(u_{0},u_{1},\ldots,u_{l},u_{l+1}=u_{0})$ in $\mathcal{C}$. Since $G$
is a chordal graph, $C$ cannot be a chordless cycle in $G$. This implies there
must exist an edge $u_{i}-u_{j}$ between two non-adjacent nodes of $C$ in $G$.
W.l.o.g., we assume $i<j$. Since the skeleton of $M$ is $G$, either
$u_{i}\rightarrow u_{j}\in M$, or $u_{j}\rightarrow u_{i}\in M$, or
$u_{i}-u_{j}\in M$.

If $u_{i}\rightarrow u_{j}\in M$ then
$(u_{0},u_{1},\ldots,u_{i},u_{j},u_{j+1},\ldots,u_{l},u_{l+1}=u_{0})$ is a
directed cycle in $M$. If $u_{j}\rightarrow u_{i}\in M$ then
$(u_{j},u_{i},u_{i+1},\ldots,u_{j})$ is a directed cycle in $M$. Both of them
contradict Observation 3.15, which asserts that $M$ is a chain graph.

Thus, the only option that remains is $u_{i}-u_{j}\in M$. But, then, $C$ is
not a chordless cycle in $\mathcal{C}$, contradicting our assumption that
$\mathcal{C}$ is not chordal. This completes the proof of Observation 3.16. ∎

###### Proof of Observation 3.17.

Suppose $M$ has an induced subgraph $a\rightarrow b-c$. Since $I=V_{G_{1}}\cap
V_{G_{2}}$ is a vertex separator of $G$, either $a,b,c\in V_{G_{1}}$, or
$a,b,c\in V_{G_{2}}$, or $a\in V_{G_{1}}\setminus I$, $b\in I$ and $c\in
V_{G_{2}}\setminus I$. We one by one show that none of the possibilities
occurs.

Suppose $a\rightarrow b-c$ is an induced subgraph of $M$ such that $a,b,c\in
V_{G_{1}}$. Since the skeleton of $M_{1}$ and the skeleton of $M[V_{G_{1}}]$
both are the same, from Corollaries 5.19 and 5.20, either $a\rightarrow b-c$
or $a-b-c$ is an induced subgraph of $M_{1}$. Since $M_{1}$ is an MEC, from
item 3 of Theorem 2.2, $a\rightarrow b-c$ is cannot be an induced subgraph of
$M_{1}$. Thus, the only option that remains is $a-b-c$ is an induced subgraph
of $M_{1}$. This implies $a,b$ and $c$ belong to the same undirected connected
component $\mathcal{C}$ of $M_{1}$. From the construction of $M$,
$\textup{skeleton}({M[V_{\mathcal{C}}]})=\mathcal{C}$. This implies
$a-b,b-c\in\mathcal{C}$ (there cannot exist a directed edge between two nodes
of the same undirected connected component of an MEC, otherwise, we get a
directed cycle, contradicting item 1 of Theorem 2.2). Since
$a-b\in\mathcal{C}$, and $a\rightarrow b\in M$, from Claim 5.25,
$V_{\mathcal{C}}\cap r_{1}\neq\varnothing$. From Observation 5.26,
$a\rightarrow b$ is added to $M$ either at step 1 of the construction of $M$,
or at step 2 of the construction of $M$ when $\mathcal{C}$ has been
considered.

Suppose $a\rightarrow b$ is added to $M$ at step 1 of the construction of $M$.
This implies $a\rightarrow b\in U_{M}(M_{1},M_{2},O)$. Then, from Observation
5.27, $a\rightarrow b\in O$. This implies $a,b\in r_{1}\cup N(r_{1},G_{1})$.
This further implies $c\notin r_{1}\cup N(r_{1},G_{1})$. Otherwise,
$a\rightarrow b-c$ is an induced subgraph of $O$, contradicting Definition 2.3
(recall that $O$ is a partial MEC). This implies $a,b\in V_{\mathcal{C}}\cap
V_{O}=V_{\mathcal{C}}\cap(r_{1}\cup N(r_{1},G_{1}))$, and $c\in
V_{\mathcal{C}}\setminus{r_{1}\cup N(r_{1},G_{1})}$. From Claim 5.40,
$\tau(a)<\tau(c)$, and $\tau(b)<\tau(c)$. Then, at step 2 of the construction
of $M$, when $\mathcal{C}$ has been considered, while running step 2(b)i, we
get $b\rightarrow c\in M$, a contradiction, since $b-c\in M$.

Suppose $a\rightarrow b$ is added to $M$ at step 2 of the construction of $M$.
Let $\tau$ be the LBFS ordering of $\mathcal{C}$ returned at step 2a of the
construction of $M$. Then, $\tau(a)<\tau(b)$. There cannot be
$\tau(c)<\tau(b)$, otherwise, from Definition 2.10, we have
$a-c\in\mathcal{C}$, which implies $a-b-c$ is not an induced subgraph of $M$,
a contradiction. This further implies $\tau(b)<\tau(c)$. Then, while running
step 2(b)i, we get $b\rightarrow c\in M$, a contradiction, since $b-c\in M$.
In every case, we get a contradiction. This implies that the possibility that
$a,b,c,\in V_{G_{1}}$ cannot occur.

Similarly, we can claim that $a,b,c\notin V_{G_{2}}$. And, if
$a=V_{G_{1}}\setminus{I}$, $b\in I$, and $c\in V_{G_{2}}\setminus I$ then
$a,b,c\in V_{O}$. From Observation 3.13, $O$ is an induced subgraph of $M$.
This implies $a\rightarrow b-c\in O$. But, this is a contradiction, as $O$ is
a partial MEC (Definition 2.3). This implies this case also cannot occur. This
further implies that there cannot exist an induced subgraph $a\rightarrow b-c$
in $M$. This completes the proof of Observation 3.17. ∎

###### Proof of Observation 3.18.

Suppose $u\rightarrow v$ is a directed edge in $M$. From the construction of
$M$, there are two possibilities: either $u,v\in V_{G_{1}}$, or $u,v\in
V_{G_{2}}$. W.l.o.g., let us assume $u,v\in V_{G_{1}}$.

Suppose $u,v\in V_{G_{1}}$ and $u\rightarrow v\in M$. From Corollary 5.19,
either $u\rightarrow v\in M_{1}$ or $u-v\in M_{1}$. We show that in both cases
$u\rightarrow v$ is strongly protected in $M$.

  1. 1.

Suppose $u\rightarrow v\in M_{1}$. According to item 4 of Theorem 2.2,
$u\rightarrow v$ is strongly protected in $M_{1}$. From Observation 5.18, a
directed edge in $M_{1}$ is a directed edge in $M$. Now, let’s consider the
induced subgraphs shown in (a), (b), (c), and (d) of fig. 1.

Suppose $u\rightarrow v$ is strongly protected in $M_{1}$ due to its inclusion
in an induced subgraph shown in (a), (b), or (c) of fig. 1. From the
construction of $M$,
$\textup{skeleton}({M_{1}})=\textup{skeleton}({M[V_{M_{1}}]})$. And, from
Observation 5.18, a directed edge in $M_{1}$ is a directed edge in $M$. This
implies that the induced subgraph is also an induced subgraph of $M$. This
further implies $u\rightarrow v$ is also strongly protected in $M$.

Now, let’s focus on the case where $u\rightarrow v$ is strongly protected in
$M_{1}$ because it is part of the induced subgraph shown in fig. 1-(d). In
this induced subgraph, the edges $w\rightarrow v$, $w^{\prime}\rightarrow v$,
and $u\rightarrow v$ are directed, indicating that $w\rightarrow v$,
$w^{\prime}\rightarrow v$, and $u\rightarrow v$ are also present in $M$ (from
Observation 5.18). To establish the strong protection of $u\rightarrow v$ in
$M$, we consider different cases. If $w-u$ and $w^{\prime}-u$ are present in
$M$, then $u\rightarrow v$ is part of the induced subgraph shown in fig.
1-(d), making it strongly protected in $M$. If $u\rightarrow w$ or
$u\rightarrow w^{\prime}$ exists in $M$, then again $u\rightarrow v$ is part
of an induced subgraph, either as shown in fig. 1-(c) with $u\rightarrow
w\rightarrow v\leftarrow u$, or as shown in fig. 1-(c) with $u\rightarrow
w^{\prime}\rightarrow v\leftarrow u$. In both cases, $u\rightarrow v$ is
strongly protected in $M$.

The remaining possibility is that both $w\rightarrow u$ and
$w^{\prime}\rightarrow u$ are present in $M$. We show that this case cannot
occur. Since $w-u-w^{\prime}$ is present in $M_{1}$, it implies that $w$, $u$,
and $w^{\prime}$ belong to the same undirected connected component
$\mathcal{C}$ of $M_{1}$.

Suppose $w,u,w^{\prime}\in r_{1}\cup N(r_{1},G_{1})=V_{O_{1}}$. Since
$O_{1}=M_{1}[r_{1}\cup N(r_{1},G_{1})]$, $w-u-w^{\prime}$ is an induced
subgraph in $O_{1}$. Also, $r_{1}\cup N(r_{1},G_{1})\subseteq V_{O}$, and from
Observation 3.13, $O$ is an induced subgraph of $M$. This implies
$w\rightarrow u\leftarrow w^{\prime}$ is an induced subgraph of $O$. But, this
is a contradiction, as since $O\in\mathcal{E}(O_{1},O_{2})$, from item 2,
$\mathcal{V}(O_{1})=\mathcal{V}(O[V_{O_{1}}])$. This implies $w,u,w^{\prime}$
all are not in $r_{1}\cup N(r_{1},G_{1})$.

Suppose all the nodes $w,u,w^{\prime}$ are not in $r_{1}\cup N(r_{1},G_{1})$.
If for an edge $x-y$ of $M_{1}$, $x\rightarrow y$ is added to $M$ at step 1 of
the construction of $M$ then $x\rightarrow y\in U_{M}(M_{1},M_{2},O)$. From
Observation 5.27, $x\rightarrow y\in O$. This implies $x,y\in V_{O}\cap
V_{M_{1}}=r_{1}\cup N(r_{1},G_{1})$. As per our assumption, not all the nodes
$w,u,w^{\prime}$ are in $r_{1}\cup N(r_{1},G_{1})$. This implies at least one
edge among $w\rightarrow u$ and $w^{\prime}\rightarrow u$ added to $M$ at step
2 of the construction of $M$. W.l.o.g., let us assume $w\rightarrow u$ is
added to $M$ at step 2 of the construction of $M$. Then, from the precondition
of item 2b, $\tau(w)<\tau(u)$, and $u\in V_{\mathcal{C}}\setminus{r_{1}\cup
N(r_{1},G_{1})}$. And, since $w^{\prime}\rightarrow u\in M$, from Claim 5.41,
$\tau(w^{\prime})<\tau(u)$. But, then, from Definition 2.10,
$w-w^{\prime}\in\mathcal{C}$, a contradiction, as $w-u-w^{\prime}$ is an
induced subgraph in $M_{1}$. This implies this case cannot occur.

In conclusion, we have shown that in all possible cases, if $u\rightarrow v$
is strongly protected in $M_{1}$, then it is also strongly protected in $M$.
Hence, the claim is verified.

  2. 2.

Suppose $u-v\in M_{1}$. This implies $u$ and $v$ belong to the same undirected
connected component $\mathcal{C}$ of $M_{1}$. $u\rightarrow v$ has been added
to $M$ either at step 1 of the construction of $M$, or at step 2 of the
construction of $M$.

If $u\rightarrow v$ is added to $M$ at step 1 of the construction of $M$ then
$u\rightarrow v\in U_{M}(M_{1},M_{2},O)$. From Observation 5.27, $u\rightarrow
v\in O$. This implies $u,v\in V_{O}\cap V_{M_{1}}=V_{O_{1}}$. Since $O_{1}$ is
an induced subgraph of $M_{1}$, this implies $u-v\in O_{1}$ and $u\rightarrow
v\in O$. Then, from item 3 of Definition 3.8, $u\rightarrow v$ is strongly
protected in $O$. From Observation 3.13, $O$ is an induced subgraph of $M$.
This implies $u\rightarrow v$ is strongly protected in $M$ as well.

Suppose $u\rightarrow v$ is added to $M$ at step 2 of the construction of $M$.
Then either it is part of an induced subgraph $w\rightarrow u\rightarrow v$
(from step 2(b)i), as shown in fig. 1.a, or it is part of an induced subgraph
$u\rightarrow w\rightarrow v\leftarrow u$ in $M$ (from step 2(b)ii), as shown
in fig. 1.c. In both cases, $u\rightarrow v$ is strongly protected in $M$.

We show that in all the possibilities, if $u\rightarrow v\in M$ then it is
strongly protected in $M$. This completes the proof of Observation 3.18. ∎

###### Proof of Observation 3.19.

We first prove that $\mathcal{P}(M,V_{G_{1}})=M_{1}$. Since $M_{1}$ is an MEC
of $G_{1}$, from Definition 2.5, to prove $\mathcal{P}(M,V_{G_{1}})=M_{1}$, we
only need to show $\mathcal{V}(M_{1})=\mathcal{V}(M[V_{G_{1}}])$.

We first show that $\mathcal{V}(M_{1})\subseteq\mathcal{V}(M[V_{G_{1}}])$.
From step 1 of the construction of $M$, all directed edges of $M_{1}$ are also
directed edges of $M$. This implies
$\mathcal{V}(M_{1})\subseteq\mathcal{V}(M[V_{G_{1}}])$, as from the
construction of $M$,
$\textup{skeleton}({M_{1}})=\textup{skeleton}({M[V_{G_{1}}]})$.

We now show that $\mathcal{V}(M[V_{G_{1}}])\subseteq\mathcal{V}(M_{1})$.
Suppose $\mathcal{V}(M[V_{G_{1}}])\nsubseteq\mathcal{V}(M_{1})$. Then, there
must exist $u,v,w\in V_{G_{1}}$ such that $u\rightarrow v\leftarrow w$ is a
v-structure in $M[V_{G_{1}}]$, and $u\rightarrow v\leftarrow w\notin M_{1}$.
From Corollary 5.19, either $u\rightarrow v\in M_{1}$ or $u-v\in M_{1}$.
Similarly, either $v\leftarrow w\in M_{1}$, or $v-w\in M_{1}$. Since
$u\rightarrow v\leftarrow w\notin M_{1}$ (from our assumption), either
$u\rightarrow v-w\in M_{1}$, or $u-v\leftarrow w\in M_{1}$, or $u-v-w\in
M_{1}$. Since $M_{1}$ is an MEC, from item 3 of Theorem 2.2, the first two
possibilities are not possible. Thus, the only option that remains is
$u-v-w\in M_{1}$. This implies $u,v,w$ belongs to the same undirected
connected component (say $\mathcal{C}$) of $M_{1}$.

$u\rightarrow v$ and $w\rightarrow v$ have not been added to $M$ at step 1 of
the construction of $M$. Otherwise, $u\rightarrow v,w\rightarrow v\in
U_{M}(M_{1},M_{2},O)$. But, then, from Observation 5.27, $u\rightarrow
v,w\rightarrow v\in O$. This further implies $u,v,w\in V_{G_{1}}\cap
V_{O}=V_{O_{1}}$. Since $O_{1}$ is an induced subgraph of $M_{1}$, this
implies $u\rightarrow v\leftarrow w$ is a v-structure in $O[V_{O_{1}}]$ and
not in $O_{1}$. This contradicts item 2 of Definition 3.8, as $O$ is an
extension of $O_{1}$ and $O_{2}$. This implies that out of $u\rightarrow v$
and $w\rightarrow v$, at least one has been added to $M$ at step 2 of the
construction of $M$.

W.l.o.g., let us assume $u\rightarrow v$ is added to $M$ at step 2 of the
construction of $M$. Then, from the precondition of item 2b,
$\tau(u)<\tau(v)$, and $v\in V_{\mathcal{C}}\setminus{r_{1}\cup
N(r_{1},G_{1})}$. And, since $w\rightarrow v\in M$, from Claim 5.41,
$\tau(w)<\tau(v)$. But, then, from Definition 2.10, $u-w\in\mathcal{C}$. From
the construction of $M$,
$\textup{skeleton}({M[V_{\mathcal{C}}]})=\mathcal{C}$. This further implies
there cannot be an induced subgraph $u\rightarrow v\leftarrow w$ in $M$,
contradicting our assumption. This implies our assumption is wrong. This shows
$\mathcal{V}(M[V_{G_{1}}])\subseteq\mathcal{V}(M_{1})$. This further implies
$\mathcal{V}(M[V_{G_{1}}])=\mathcal{V}(M_{1})$.

Similarly, we can show that $\mathcal{P}(M,V_{G_{2}})=M_{2}$. This completes
the proof of Observation 3.19. ∎

###### Proof of Observation 3.20.

Since $M\in\text{MEC}(G,O)$ and
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$,
$\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\mathcal{V}(O)\subseteq\mathcal{V}(M)$.
Suppose $u\rightarrow v\leftarrow w$ is a v-structure in $M$. Since
$I=r_{1}\cap r_{2}$ is a vertex separator of $G$, either $u,v,w\in V_{G_{1}}$
or $u,v,w\in V_{G_{2}}$, or $u,v,w\in V_{O}$. Since
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$, if $u,v,w\in V_{G_{1}}$
then $u\rightarrow v\leftarrow w$ is a v-structure in $M_{1}$, if $u,v,w\in
V_{G_{2}}$ then $u\rightarrow v\leftarrow w$ is a v-structure in $M_{2}$, and
if $u,v,w\in V_{O}$ then $u\rightarrow v\leftarrow w$ is a v-structure in $O$.
This implies
$\mathcal{V}(M)\subseteq\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\mathcal{V}(O)$.
This further implies
$\mathcal{V}(M)=\mathcal{V}(M_{1})\cup\mathcal{V}(M_{2})\cup\mathcal{V}(O)$.
As discussed in the introduction, given a skeleton and a set of v-structures,
there exists a unique MEC with that skeleton and v-structures. This implies
that $M$ is unique. ∎

###### Proof of Lemma 3.21.

We use Definition 3.8 to define a bijective function $f_{O}$. We use the
function for the computation of $|\text{MEC}(G,O)|$.

######  Definition 5.46 (Function $f_{O}$).

Let $G$ be a chordal graph, and $G_{1}$ and $G_{2}$ be two induced subgraphs
of $G$ such that $G=G_{1}\cup G_{2}$, and $I=V_{G_{1}}\cap V_{G_{2}}$ is a
vertex separator of $G$ that separates $V_{G_{1}}\setminus I$ and
$V_{G_{2}}\setminus I$. Let $r_{1}$ and $r_{2}$ be cliques of, respectively,
$G_{1}$ and $G_{2}$ such that $r_{1}\cap r_{2}=I$. Let $X_{1}=r_{1}\cup
N(r_{1},G_{1})$, $X_{2}=r_{2}\cup N(r_{2},G_{2})$, and $X=r_{1}\cup r_{2}\cup
N(r_{1}\cup r_{2},G)$. Consider $O\in\text{PMEC}(G[X])$. Define
$T_{1}=\text{MEC}(G,O)$ and $T_{2}=\\{(M_{1},M_{2}):$ $\exists(O_{1},O_{2})\in
O_{1}\in\text{PMEC}(G_{1}[X_{1}])\times\text{PMEC}(G_{2}[X_{2}])$ such that
$O\in\mathcal{E}(O_{1},O_{2})$, $M_{1}\in\text{MEC}(G_{1},O_{1})$, and
$M_{2}\in\text{MEC}(G_{2},O_{2})\\}$. The function $f_{O}:T_{1}\rightarrow
T_{2}$ is defined as $f_{O}(M)=(M_{1},M_{2})$ if
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$.

######  Lemma 5.47.

$f_{O}$ is bijective.

###### Proof.

We first prove $\rightarrow$ of Lemma 5.47.

######  Claim 5.48.

For each $M\in\text{MEC}(G,O)$, there exists a unique $(M_{1},M_{2})$ such
that $f_{O}(M)=(M_{1},M_{2})$.

###### Proof.

Let $M\in\text{MEC}(G,O))$. This implies $M$ is an MEC of $G$, and
$M[V_{O}]=O$. Let $\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$. From
Observation 2.6, there exists a unique $(M_{1},M_{2})$ such that
$\mathcal{P}(M,V_{G_{1}},V_{G_{2}})=(M_{1},M_{2})$. Thus, we only have to show
that $(M_{1},M_{2})\in T_{2}$. Let $O_{1}=M_{1}[X_{1}]$ and
$O_{2}=M_{2}[X_{2}]$. From Corollary 3.5, $O_{1}\in\text{PMEC}(G_{1}[X_{1}])$,
and $O_{2}\in\text{PMEC}(G_{2}[X_{2}])$. This implies
$M_{1}\in\text{MEC}(G_{1},O_{1})$ and $M_{2}\in\text{MEC}(G_{2},O_{2})$. From
Lemma 3.9, $O\in\mathcal{E}(O_{1},O_{2})$. From the definition of $T_{2}$
(given at Definition 5.46), $(M_{1},M_{2})\in T_{2}$. Thus, from Definition
5.46, $f_{O}(M)=(M_{1},M_{2})$.

∎

We now prove $\leftarrow$ of Lemma 5.47.

######  Claim 5.49.

Let $O_{1}$ be a partial MEC of $G_{1}[X_{1}]$ and $O_{2}$ be a partial MEC of
$G_{2}[X_{2}]$ such that $O$ is an extension of $(O_{1},O_{2})$. For each
$M_{1}\in\text{MEC}(G_{1},O_{1})$ and $M_{2}\in\text{MEC}(G_{2},O_{2})$, there
exists a unique $M\in\text{MEC}(G,O)$ such that $f_{O}(M)=(M_{1},M_{2})$.

###### Proof.

Lemmas 3.10 and 5.46 imply Claim 5.49. ∎

Claims 5.48 and 5.49 prove Lemma 5.47. ∎

From Lemma 5.47, $|T_{1}|=|T_{2}|$. Since $T_{1}=\text{MEC}(G,O)$, therefore,
$|T_{1}|=|\text{MEC}(G,O)|$. Since $T_{2}$ contains tuples $(M_{1},M_{2})$
such that for some tuple
$(O_{1},O_{2})\in\text{PMEC}(G_{1}[X_{1}])\times\text{PMEC}(G_{2}[X_{2}])$,
and $O\in\mathcal{E}(O_{1},O_{2})$, $M_{1}\in\text{MEC}(G_{1},O_{1})$ and
$M_{2}\in\text{MEC}(G_{2},O_{2})$. This implies

$T_{2}=\bigcup_{\begin{subarray}{c}O_{1}\in\text{PMEC}(G_{1}[X_{1}])\\\
O_{2}\in\text{PMEC}(G_{2}[X_{2}])\\\
O\in\mathcal{E}(O_{1},O_{2})\end{subarray}}{\text{MEC}(G_{1},O_{1})\times\text{MEC}(G_{2},O_{2})}.$
(18)

We show that sets $\text{MEC}(G_{1},O_{1})\times\text{MEC}(G_{2},O_{2})$ are
disjoint. Suppose sets $\text{MEC}(G_{1},O_{1})\times\text{MEC}(G_{2},O_{2})$
are not disjoint. Then there exists $(M_{1},M_{2})$ such that
$(M_{1},M_{2})\in\text{MEC}(G_{1},O_{1})\times\text{MEC}(G_{2},O_{2})$ as well
as
$(M_{1},M_{2})\in\text{MEC}(G_{1},O_{1}^{\prime})\times\text{MEC}(G_{2},O_{2}^{\prime})$.
This implies $M_{1}\in\text{MEC}(G_{1},O_{1})$ as well as
$M_{1}\in\text{MEC}(G_{1},O_{1}^{\prime})$. But, from Corollary 3.4, image of
$M$ on $X_{1}$ is unique, i.e., $O_{1}=O_{1}^{\prime}$. Similarly, we can say
that $O_{2}=O_{2}^{\prime}$. This shows
$(O_{1},O_{2})=(O_{1}^{\prime},O_{2}^{\prime})$. This implies that the sets
$\text{MEC}(G_{1},O_{1})\times\text{MEC}(G_{2},O_{2})$ are disjoint. This
further implies

$|T_{2}|=\bigcup_{\begin{subarray}{c}O_{1}\in\text{PMEC}(G_{1}[X_{1}])\\\
O_{2}\in\text{PMEC}(G_{2}[X_{2}])\\\
O\in\mathcal{E}(O_{1},O_{2})\end{subarray}}{|\text{MEC}(G_{1},O_{1})|\times|\text{MEC}(G_{2},O_{2})|}.$
(19)

This proves Lemma 3.21. ∎

###### Proof of Lemma 3.22.

We start with the following:

$\text{MEC}(G,O^{\prime})=\bigcup_{\begin{subarray}{c}O\in\text{PMEC}(G[X])\\\
O^{\prime}=O[X^{\prime}]\end{subarray}}{\text{MEC}(G,O)}.$ (20)

We first show that the L.H.S. of eq. 20 is a subset of the R.H.S. of eq. 20.

######  Lemma 5.50.

Let $G$ be a chordal graph, $X^{\prime}\subseteq X\subseteq V_{G}$, and
$O^{\prime}\in\text{PMEC}(G[X])$. Let $M\in\text{MEC}(G,O^{\prime})$. Then,
there exists a partial MEC $O\in\text{PMEC}(G[X])$ such that $O^{\prime}=O[X]$
and $M\in\text{MEC}(G,O)$.

###### Proof.

Since $O^{\prime}$ is an image of $M$, from Definition 3.3,
$M[X^{\prime}]=O^{\prime}$. Let $O=M[X]$. From Definition 3.3, $O$ is an image
of $M$, and $M\in\text{MEC}(G,O)$. From Corollary 3.5,
$O\in\text{PMEC}(G[X])$. Also, since $X^{\prime}\subseteq X$, and both $O$ and
$O^{\prime}$ are induced subgraph of $M$,
$O[X^{\prime}]=M[X^{\prime}]=O^{\prime}$. This proves Lemma 5.50. ∎

We now show that the R.H.S. of eq. 20 is a subset of the L.H.S. of eq. 20.

######  Lemma 5.51.

Let $G$ be a chordal graph, $X^{\prime}\subseteq X\subseteq V_{G}$,
$O\in\text{PMEC}(G[X])$, and $O^{\prime}\in\text{PMEC}(G[X^{\prime}])$ such
that $O^{\prime}=O[X^{\prime}]$. Then, $M\in\text{MEC}(G,O^{\prime})$.

###### Proof.

Since $M\in\text{MEC}(G,O)$, and $O=M[V_{O}]=M[X]$. Also, since
$O^{\prime}=O[X^{\prime}]$, and $X^{\prime}\subseteq X$,
$O^{\prime}=M[X^{\prime}]$. This implies $O^{\prime}$ is an image of $M$,
i.e., $M\in\text{MEC}(G,O^{\prime})$. This proves Lemma 5.51. ∎

Lemmas 5.50 and 5.51 imply eq. 20.

From Corollary 3.4, each MEC has a unique image on $X$. This implies the
R.H.S. of eq. 20 is a disjoint union of sets $\text{MEC}(G,O)$ for
$O\in\text{PMEC}(G[X])$. This further implies eq. 5. This completes the proof
of Lemma 3.22. ∎

###### Proof of Lemma 3.23.

From Lemma 3.22, since $X^{\prime}\subseteq X\subseteq V_{G}$, we have

$|\text{MEC}(G,O^{\prime})|=\sum_{\begin{subarray}{c}O\in\text{PMEC}(G[X])\\\
O^{\prime}=O[X^{\prime}]\end{subarray}}{|\text{MEC}(G,O)|}.$ (21)

Now, from Lemma 3.21,

$|\text{MEC}(G,O)|=\sum_{\begin{subarray}{c}O_{1}\in\text{PMEC}(G_{1}[X_{1}])\\\
O_{2}\in\text{PMEC}(G_{2}[X_{2}])\\\
O\in\mathcal{E}(O_{1},O_{2})\end{subarray}}{|\text{MEC}(G_{1},O_{1})|\times|\text{MEC}(G_{2},O_{2})|}.$
(22)

Combining eqs. 21 and 22, we get eq. 6. This completes the proof of Lemma
3.23. ∎

###### Proof of Lemma 3.24.

At line 2, we construct the required function $f$, and for each partial MEC
$O\in\text{PMEC}(G[r_{1}\cup N(r_{1},G)])$, we initialized it (at lines 2-2)
with $f(O)=0$. Lines 2-2 deal with the base case, when the degree of $r_{1}$
in $T$ is zero.

If the degree of $r_{1}$ in $T$ is zero then $V_{G}=r_{1}$, and $G$ is a
clique. For a clique graph $G$, there exists only one MEC of $G$ that is $G$
itself.

Suppose $M$ is an MEC of a clique graph $G$, and there exists a directed edge
in $M$. Pick an edge $u\rightarrow v\in M$ such that $u$ does not have any
incoming edge, and there does not exist any incoming edge to $v$ from the
neighbors of $u$. Since $M$ is a chain graph (from item 1 of Theorem 2.2), we
must get such $u\rightarrow v$. But, then $u\rightarrow v$ is not strongly
protected. Since $M$ is an MEC of a clique graph $G$, $u\rightarrow v$ cannot
be part of any induced subgraph as shown fig. 1.a, fig. 1.b, and fig. 1.d.
And, $u\rightarrow v$ cannot be part of any induced subgraph as shown fig. 1.c
because of the choice of $u$ and $v$. This implies $M$ cannot have any
directed edge. This further implies each edge of $M$ is undirected, i.e., $M$
is $G$ itself (since $G$ is chordal, $G$ is an MEC as it obeys items 1, 2, 3
and 4 Theorem 3.1), and $|\text{MEC}(G)|=1$. This also implies that the
induced subgraph of the only MEC $M$ of $G$ on $V_{G}$ is $G$, i.e.,
$|\text{MEC}(G,G)|=1$. This is why we update $f$ at line 2 with $f(G)=1$. This
implies that when the degree of $r_{1}$ is zero, algorithm 2 outputs the
required function.

If the degree of $r_{1}$ is not zero then algorithm 2 implements Lemma 3.23 at
lines 2 \- 2. Lemma 3.23 validates the function $f$ that is returned at line
2. This completes the proof of Lemma 3.24. ∎

###### Proof of Lemma 3.25.

At line 3, the algorithm constructs a clique tree $T$ of $G$. Then, it picks
an arbitrary node $r_{1}$ of $T$ (line 3). At line 3, it calls algorithm 3
that returns a function $f:\text{PMEC}(G[r_{1}\cup
N(r_{1},G_{1})])\rightarrow\mathbb{Z}$ such that $f(O)=|\text{MEC}(G,O)|$.
Lines 3-3 implement eq. 3 to compute $|\text{MEC}(G)|$. Line 3 returns the
required result. This completes the proof of Lemma 3.25. ∎

Input : Three partial MECs $O$, $O_{1}$, and $O_{2}$ such that $G$ is a
chordal graph, and $G_{1}$ and $G_{2}$ are two induced subgraphs of $G$ such
that $G=G_{1}\cup G_{2}$, and $I=V_{G_{1}}\cap V_{G_{2}}$ is a vertex
separator of $G$ that separates $V_{G_{1}}\setminus I$ and $V_{G_{2}}\setminus
I$. $r_{1}$ and $r_{2}$ are cliques of, respectively, $G_{1}$ and $G_{2}$ such
that $r_{1}\cap r_{2}=I$. $O\in\text{PMEC}(G[r_{1}\cup r_{2}\cup N(r_{1}\cup
r_{2},G)])$, $O_{1}\in\text{PMEC}(G_{1}[r_{1}\cup N(r_{1},G_{1})])$, and
$O_{2}\in\text{PMEC}(G_{2}[r_{2}\cup N(r_{2},G_{2})])$.

Output : 1 : if $O\in\mathcal{E}(O_{1},O_{2})$,

0 : otherwise.

1

2foreach  _$a\in\\{1,2\\}$_ do

3 if  _$\exists u\rightarrow v\in O_{a}$ such that $u\rightarrow v\notin O$_
then

4 return 0\.

5 end if

6

7 end foreach

8

9foreach  _$a\in\\{1,2\\}$_ do

10 foreach  _$u,v,w\in V_{O_{a}}$_ do

11 if  _$u\rightarrow v\leftarrow w$ is a v-structure in $O$ but not a
v-structure in $O_{a}$_ then

12 return 0\.

13 end if

14

15 end foreach

16

17 end foreach

18

19foreach  _$a\in\\{1,2\\}$_ do

20 foreach  _$u-v\in O_{a}$_ do

21 if  _$u\rightarrow v\in O$_ then

22 if  _$u\rightarrow v$ is not strongly protected in $O$ _ then

23 return 0\.

24 end if

25

26 end if

27

28 end foreach

29

30 end foreach

31

return 1\.

Algorithm 4 Is_Extension

Algorithm 4 is constructed to verify whether for any partial MECs $O$,
$O_{1}$, and $O_{2}$, $O$ is an extension (Definition 3.8) of $O_{1}$ and
$O_{2}$ or not. Lemma 5.52 validates algorithm 4.

######  Lemma 5.52.

Let $G$ be a chordal graph, and $G_{1}$ and $G_{2}$ be two induced subgraphs
of $G$ such that $G=G_{1}\cup G_{2}$, and $I=V_{G_{1}}\cap V_{G_{2}}$ be a
vertex separator of $G$ that separates $V_{G_{1}}\setminus I$ and
$V_{G_{2}}\setminus I$. Let $r_{1}$ and $r_{2}$ be cliques of, respectively,
$G_{1}$ and $G_{2}$ such that $r_{1}\cap r_{2}=I$.
$O\in\text{PMEC}(G[r_{1}\cup r_{2}\cup N(r_{1}\cup r_{2},G)])$,
$O_{1}\in\text{PMEC}(G_{1}[r_{1}\cup N(r_{1},G_{1})])$, and
$O_{2}\in\text{PMEC}(G_{2}[r_{2}\cup N(r_{2},G_{2})])$. Algorithm 4 outputs 1
if $O\in\mathcal{E}(O_{1},O_{2})$, otherwise, 0.

###### Proof.

Lines 4-4 verifies item 1 of Definition 3.8. Since from the construction, for
each $a\in\\{1,2\\}$,
$\textup{skeleton}({O_{a}})=\textup{skeleton}({O[V_{O_{a}}]})$, item 1 of
Definition 3.8 implies that
$\mathcal{V}(O[V_{O_{a}}])\subseteq\mathcal{V}(O_{a})$. Lines 4-4 verifies
$\mathcal{V}(O_{a})\subseteq\mathcal{V}(O[V_{O_{a}}])$. In this way, item 2 of
Definition 3.8 is verified. Lines 4-4 verifies item 3 of Definition 3.8. If
items 1, 2 and 3 of Definition 3.8 fails then the algorithm returns 0,
otherwise, it returns 1. This validates algorithm 4. ∎

###  5.3 Omitted proofs of Section 4

###### Proof of Lemma 4.1.

At line 1, Algorithm 1 cuts an edge of $G$. This creates two induced subgraphs
$G_{1}$ and $G_{2}$ of $G$. At lines 1-1, the algorithm recursively call
itself for $G_{1}$ and $G_{2}$. Since the number of edges in $G$ is $n-1$, the
number of times algorithm 1 recursively calls itself is $n-1$. Computation of
$N$, $b$, and $c_{0}$ (at lines 1-1) can be done in $O(d)$ time. The while
loop at lines 1-1 runs for $O(d)$ time. And, the computation of $c_{i}$ at
line 1 takes $O(d)$ time. This implies the running time of lines 1-1 is
$O(d^{2})$ time. Thus, the overall running time of algorithm 1 is $O(d^{2}n)$.
∎

###### Proof of Lemma 4.2.

At line 2 of algorithm 2, we cut an edge of $T$ to recursively call algorithm
2 (at lines 2 and 2). The number of edges in a clique tree of a chordal graph
$G$ is $O(n)$. This implies the number of times algorithm 2 is called
recursively is $O(n)$. If the treewidth of $G$ is $k$ then the size of $r_{1}$
is $k+1$. If the degree of $G$ is $d$ then the number of nodes in $r_{1}\cup
N(r_{1},G)$ is at most $(d+1)(k+1)$, i.e., $O(dk)$. And, the number of edges
in $G[r_{1}\cup N(r_{1},G)]$ is $O(d^{2}k^{2})$. Since in a partial MEC of
$G[r_{1}\cup N(r_{1},G)]$, each edge $u-v$ of $G[r_{1}\cup N(r_{1},G)]$ is
either $u-v$ or $u\rightarrow v$, or $v\rightarrow u$. This implies the number
of partial MECs of $G[r_{1}\cup N(r_{1},G)]$ is at most $3^{d^{2}k^{2}}$,
i.e., $O(2^{O(d^{2}k^{2})})$. Therefore, the running time of initialization of
$f$ (lines 2-2) is $O(2^{O(d^{2}k^{2})})$. Running time of lines 2-2 takes
$O(1)$ time. The running time of lines 2–2 is $O(|V_{G}|+|E_{G}|)$. Similar to
the partial MECs of $G[r_{1}\cup N(r_{1},G)]$, the number of partial MECs of
$G_{1}[r_{1}\cup N(r_{1},G_{1})]$, $G_{2}[r_{2}\cup N(r_{2},G_{2})]$, and
$G[r_{1}\cup r_{2}\cup N(r_{1}\cup r_{2},G)]$ is $O(2^{O(d^{2}k^{2})})$.
Therefore, each of the for loops at lines 2, 2, and 2 runs for
$O(2^{O(d^{2}k^{2})})$ time. Since the number of edges in $O,O_{1}$ and
$O_{2}$ are $O(d^{2}k^{2})$, from Lemma 5.53, we can verify whether
$O\in\mathcal{E}(O_{1},O_{2})$ (at line 2) in $O(d^{2}k^{2})$ time.
Construction of $O^{\prime}$ at line 2, can be done in $O(d^{2}k^{2})$ time.
And, updation of $f$ at line 2 runs for $O(1)$ time. This implies the overall
run time of algorithm 2 is $O(n(2^{O(d^{2}k^{2})}+n^{2}))$. This completes the
proof of Lemma 4.2. ∎

###### Proof of Lemma 4.3.

We can compute a clique tree representation of a chordal graph $G$ (line 3 of
algorithm 3) in $O(|V_{G}|+|E_{G}|)$ time Blair and Peyton [1993]. From Lemma
4.2, the running time of line 3 is $O(n(2^{O(d^{2}k^{2})}+n^{2}))$. As
discussed in the proof of Lemma 4.2, the number of partial MECs in
$G[r_{1}\cup N(r_{1},G)]$ is $O(2^{O(d^{2}k^{2})})$. This implies the running
time of lines 3-3 if $O(2^{O(d^{2}k^{2})})$. This implies the overall running
time of algorithm 3 is $O(n(2^{O(d^{2}k^{2})}+n^{2}))$. This completes the
proof of Lemma 4.3. ∎

###### Proof of Theorem 4.4.

We can pick a root node $r_{1}$ of $G$ in $O(1)$ time. Then, we call algorithm
1 for input $G$ and $r_{1}$. From Lemma 4.1, the running time of the algorithm
is $O(d^{2}n)$. The algorithm returns $n_{1}(G,r_{1})$, $n_{0}^{0}(G,r_{1})$,
$n_{0}^{1}(G,r_{1})$, …, $n_{0}^{d}(G,r_{1})$, where $d$ is the degree of
$r_{1}$ in $G$. Then, using eqs. 1 and 2, we can compute $|\text{MEC}(G)|$.
Therefore, in $O(d^{2}n)$ time, we can count the MECs of $G$. ∎

###### Proof of Theorem 4.5.

Lemmas 3.25 and 4.3 validates the theorem. ∎

######  Lemma 5.53.

The time complexity of algorithm 4 is $O(d^{3}k^{3})$.

###### Proof.

As discussed in the proof of algorithm 2, the number of nodes in $O,O_{1}$,
and $O_{2}$ is $O(dk)$, and the number of edges in them is $O(d^{2}k^{2})$.
This implies the running time of lines 4-4 is $O(d^{2}k^{2})$. The running
time of lines 4-4 is $O(d^{3}k^{3})$. Verifying each directed edge to
determine whether it is strongly protected or not cumulatively takes
$O(|V_{O}|+|E_{O}|)$ time. This implies the running time of lines 4-4 is
$O(d^{2}k^{2})$. Therefore, the overall running time of algorithm 4 is
$O(d^{3}k^{3})$. This completes the proof of Lemma 5.53. ∎