Углеродные нанотрубки

Контуром в графе называется замкнутая цепочка ребер, объединение которых представляет собой линию, гомеоморфную окружности.

Деревом называется связный граф, не содержащий ни одного контура.

Индекс точки называется число дуг, сходящихся в данной точке.

Также следует доказать следующую теорему:

Для любого дерева, имеющего В вершин и Р ребер, справедливо соотношение

В-Р=1. (2)

Для доказательства проведем индукцию по числу ребер Р. При Р=1 (дерево имеет одно ребро и две вершины) соотношение (2) справедливо. Предположим, что для любого дерева, имеющего n ребер, соотношение (2) уже доказано, и пусть G — дерево, имеющее n+1 ребро. Так как граф G связен, то его можно получить из некоторого связного графа G` добавлением одного ребра r.

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

* * *

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