Chordal graph question In the below image, the graph is being triangulated (added edges are in red). My question is simple :
Is the red edge between nodes 7 and 10 necessary in order to obtain a chordal graph?



(this image comes from Yaroslav Bulatov's excellent answer on https://cstheory.stackexchange.com/questions/5018/the-origin-of-the-notion-of-treewidth/5020#5020)
No, you can delete that edge and the graph remains chordal. This is so because you don't introduce an induced cycle of length 4 or more.