Граф называется полным, если каждые две различные вершины его соединены одним и только одним ребром. В полном графе каждая его вершина принадлежит одному и тому же числу ребер. Для задания полного графа достаточно знать число его вершин. Полный граф с n  вершинами обычно обозначается через Кn

 

Граф, не являющийся полным, можно преобразовать в полный с теми же вершинами, добавив недостающие ребра. Вершины графа  и ребра, которые добавлены, тоже образуют граф. Такой граф называют  дополнением графа    и обозначают его