![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Chordal-graph.svg/langru-640px-Chordal-graph.svg.png&w=640&q=50)
Граф Мейнеля
Материал из Википедии — свободной encyclopedia
Граф Мейнеля — это граф, в котором любой нечётный цикл длины пять и более имеет по меньшей мере две хорды, то есть два ребра, соединяющих несоседние вершины цикла[1]. Хорды могут быть непересекающимися (как на рисунке), а могут и пересекаться.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/3/34/Chordal-graph.svg/220px-Chordal-graph.svg.png)
Графы Мейнеля названы именем Генри Мейнеля (известного также по гипотезе Мейнеля), который доказал в 1976 году, что они являются совершенными графами[2] задолго до доказательства cильной гипотезы о совершенных графах, полностью описывающей совершенные графы. Тот же результат был независимо обнаружен Маркосяном и Карапетяном[3].