Полный двудольный граф

Полный двудольный граф — это двудольный граф, такой что для любых двух вершин и , является ребром в . Полный двудольный граф с долями размера и обозначается как .

· Графы называются звёздами, все полные двудольные графы, являющиеся деревьями, являются звёздами.

· Граф называется клешнёй и используется для определения графов без клешней.

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

Планарные (плоские) графы. Формула Эйлера.

Планарный граф — граф, который может быть изображён на плоскости без пересечения ребер. Иначе говоря, граф планарен, если он изоморфен некоторому плоскому графу, то есть графу, изображённому на плоскости так, что его вершины — этоточки плоскости, а рёбра — непересекающиеся кривые на ней. Области, на которые граф разбивает плоскость, называются его гранями. Неограниченная часть плоскости — тоже грань, так называемая внешняя грань.