Тривиально совершенный граф (trivially perfect graph) - это граф, в котором выполняется следующее свойство: для любых двух вершин, если они обе смежны с третьей вершиной, то они смежны и друг с другом.

Другими словами, в таком графе не может быть индуцированного пути длины 2 (P3) и индуцированного цикла длины 4 (C4).

Эквивалентные определения:

• Граф является тривиально совершенным тогда и только тогда, когда он является хордальным и не содержит P4 (путь из 4 вершин) как индуцированный подграф
• Это в точности графы сравнимости деревьев (comparability graphs of trees)

Примеры:

1. Полный граф Kn - тривиально совершенный (любые две вершины смежны)
2. Звезда K1,n - тривиально совершенный (центр смежен со всеми, листья не смежны между собой, но и не имеют общего соседа кроме центра)
3. Путь P3 (три вершины в ряд) - НЕ тривиально совершенный, потому что крайние вершины обе смежны с центральной, но не смежны друг с другом

Название "тривиально совершенный" происходит от того, что для таких графов задача нахождения максимальной клики и хроматического числа решается тривиально (за линейное время).