Теория графов

[Monster]

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

[Chernoknizhnik]

Индукцией по количеству вершин просто доказывается.

[Monster]

Я пробовал.У меня не получилось.Объясните пожалуйста доказательство.

[Chernoknizhnik]

Найдите три вершины многоугольника $X_{i-1}$,$X_{i}$,$X_{i+1}$ ($i+1$ примем за $1$, если $i=n$), такие, что $X_{i-1}$ и $X_{i+1}$ соединены диагональю. Отсекаем этот треугольник, выбрав в нем точку. В оставшемся куске у нас лежит, по предположению индукции, связный граф без циклов. Ну а для квадрата (база индукции) это очевидно.

[iifat]

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