Пусть G = G(V,E) – неориентированный граф с вершинами v0, v1, v2, v3, …, vk множества V и ребрами e1, e2, e3, …, ek множества Е. Определение. Путем (маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…v(k-1)ekvk такая, что eі = {ѵі-1, vі}. Таким образом, путь длины k имеет k ребер. Определение. Если нет рёбер, предшествующих e1, то вершина v0 называется начальной, если нет рёбер, следующих после ek, то вершина vk называется конечной, вершины пути, не являющиеся начальной или конечной, называются внутренними...

В графе 18 вершин, причём степень каждой вершины равна 2 или 5, вершины обеих степеней присутствуют. Сколько компонент связности может быть в таком графе? Во-первых могут быть связаны все вершины. Это 1 компонента связности. Потом мы можем отделить 3 вершины, у которых степени будут по 2 и они образуют треугольный подграф, а остальные 15 вершин будут все связаны между собой. Это 2 компоненты. Мы можем отделить 2 таких треугольника. Останется 12 связанных вершин, среди которых будет хотя бы одна вершина со степенью 5. Это будет 3 компоненты. Ничего не мешает взять и 3 таких треугольника...