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.)?

  • 1
    $\begingroup$ 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... $\endgroup$ Mar 17 '19 at 14:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.