Пример 3

Пример 3.

Заметим, что степень каждой вершины полного графа равна , так что

.

Следовательно, число ребер полного графа с вершинами равно .

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

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

Полный двудольный граф с вершинами в одной доле и вершинами в другой () обозначают .

Пример 3.

Граф, вершины которого - помеченные точки плоскости или пространства, а ребра – непрерывные кривые, соединяющие данные точки (причем не проходящие через другие вершины), называется геометрическим.