Графы

[lostoman]

Народ, помогите пожалуйста решить задачи по теории графов. Может какие-нибудь из нижеприведенных вы знаете как решать
1)G-внешнепланарный граф, доказать что существует вершина степени <= 2
2) G - не 4-ч связнаю триангуляция, доказать что существует разделяющий трегольник
3) G - критический, m(число ребер) <= 2n-4, n -число вершин
4)Привести пример графа: кубический, 3-х связный, двудольный, негамильтонов
5)G-плоский, гамильтонов, доказать что его грани можно раскрасит в 4 цвета
6)e(G) = e(G^3) описать такие графы, e(G) -число вершинной независимости в графе

[V.V.]

Почитайте книгу Харари "Теория графов"