Chordal Graph to Directed Acyclic Graph I have seen an exercise which says an undirected graph $G=(V,E)$ is chordal if and only if the edges of $G$ can be oriented with directions, such that the resulting graph $D=(V,A)$ has the following properties:


*

*$D$ is acyclic

*if $(x,y)$ and $(x,z)$ belong to $A$, then $(y,z)$ or $(z,y)$ belongs to $A$
The sufficiency is very easy since if we have a directed graph with these properties, we can assume the graph is not chordal (there exists cycle with length $\geq 4$ without a chord), and start assigning directions to the edges in this cycle. In the end, we will need to have $D$ has a directed cycle and this will contradict.
However, the necessity is very hard to prove. If we are given that $G$ is chordal, how can we prove the orientation? Shall we give an algorithm to orient the edges, or is there a shortcut (contradiction etc.)?

If G is chordal, to construct D: take a perfect elimination ordering and label the vertices by their index in it. Now orient all the edges by increasing labels, that is, assuming $i < j$ : $\{v_i,v_j\} \Rightarrow (v_i,v_j)$.
The property is satisfied, and D is acyclic since any cycle would contain a decreasing edge, which does not exist in D.
