Dwa zadanka z teorii grafów

[olo150892]

Zad. 1
Pokazać, że w dowolnym prostym grafie planarnym istnieje wierzchołek stopnia co najwyżej 5.

Zad. 2
Pokazać, że jeżeli G jest grafem prostym n-wierzchołkowym dla którego zachodzi:
\(\displaystyle{ d(G) \ge n-2}\) to \(\displaystyle{ \alpha (G)=d(G)}\), gdzie \(\displaystyle{ d(G)}\)-min. stopień wierzchołka w grafie, a \(\displaystyle{ \alpha (G)=max\left\{k \in N _{0}:G \ jest \ k-spojny\right\}}\)

Zupełnie nie wiem, jak się do tego zabrać. Proszę o jakąś pomoc, wskazówki itd.

[norwimaj]

1. Zakładając, że każdy wierzchołek ma stopień co najmniej \(\displaystyle{ 6}\), pokaż, że \(\displaystyle{ m\ge3n}\), gdzie \(\displaystyle{ m}\) - liczba krawędzi, \(\displaystyle{ n}\) - liczba wierzchołków.