Skip to main content
1 of 2

The result that each N - free partial order is the edge - partial order of an unique e - bipolarly oriented graph, implies that a poset is an edge poset if and only if it is N-free.

Proof:$(\Rightarrow)$ We prove that edge posets are N-free by contradiction. Suppose $P$ is the edge-poset of acyclic directed graph $G$ and is not N-free, then it contains a covering-subposet $N$ with four elements $\{a,b,c,d\}$ such that $a$ covers $b$, $c$ covers $b$, $c$ covers $d$, $a||c$, $a||d$ and $b||d$. Evidently, the edges conrresponding to $a,b,c,d$ and their end-vertices form a sub acyclic directed graph of $G$, whose edge-poset is $N$. This contradicts with the fact that $N$ can not be an edge-poset.

$(\Leftarrow)$ This direction is a direct consequence of the fact that any N-free poset is the edge poset of an unique PERT-graph.

The conrrespondence between N-free posets and acyclic directed graphs are one-to-many. In fact, we can freely combine and split the sources and sinks of an acyclic directed graph without changing its edge-poset. It is natural to introduce the following notion.

Two acyclic directed graphs are EP-equivalent if they have the same edge-poset.