# 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:

1. $$D$$ is acyclic
2. 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.)?

• Okay I am close to the proof. Every chordal graph contains a simplicial vertex. Take a simplicial vertex and push the direction outwards. Delete this vertex, move to the next simplicial vertex. This will follow the axioms... – independentvariable Mar 17 at 14:28