Хордальный граф

Цикл (черный) с двумя хордами (зеленые). В данном случае граф хордальный, хотя удаление одного зеленого ребра нарушит это свойство. Действительно, в этому случае зеленое ребро с тремя черными образуют цикл длины 4 без хорд.

Хордальный граф

Хордальный граф — это граф, в котором все циклы, состоящие более чем из 3 ребер, содержат хорду. Хорда в данном случае - это ребро, соединяющее две вершины, не смежные в первоначальном цикле.