Определение. Если (а, b) – ориентированное ребро, тогда вершина а называется начальной вершиной ориентированного графа, а вершина b – конечной вершиной ребра (а, b). Ориентированное ребро (а, b) называют также инцидентным вершинам а и b. Обратно, говорят, что вершины а и bинцидентны ориентированному ребру (а, b). Пример 1. Рассмотрим ориентированный граф G1, который состоит из множества вершин V(G1), содержащего 6 элементов, и множества рёбер E(G1), содержащего 6 элементов: V(G1) = {a, b, c, d, e, f}, E(G1) = {(a, b), (a, c), (b, d), (c, d), (e, c), (f, d)}...

Возможно, придет время для разговора о неплоских графинях, их телах и прочих неплатонических материях — но потом. Не сейчас. Сейчас давайте побеседуем о графах. Мы уже обсудили проблему четырех красок и там же доказали теорему о пяти и дале контрпример к трем. И остался один нюансик: почему у плоского графа непременно есть вершина, из которой выходит менее шести ребер? В общем-то, нарисовать граф, у которого ребра не пересекаются и из каждой вершины их выходит пять — задачка со звездочкой. Попробуйте...