Ile maksymalnie krawędzi można dorysować do poniższego drzewa tak,aby otrzymany graf nadal był planarny? Byłabym wdzięczna za wytłumaczenie również tego zadania. Pozdrawiam

Max liczba gałęzi wynosi 8 a to wynika z definicji grafu planarnego to znaczy linie nie mogą się przecinać. 

Zachodzi nierówność [latex]|E|leq 3|V|-6[/latex], gdzie |E| jest liczbą krawędzi, a |V| liczbą wierzchołków (to wynika jakoś ze wzoru Eulera). W tym przypadku [latex]|E|leq 3cdot 12-6=30[/latex], zatem krawędzi będzie na pewno nie więcej niż 30 (z czego wynika, że można by dorysować maksymalnie 19 gałęzi). Trzeba jeszcze pokazać, że faktycznie da się rozszerzyć ten graf do grafu o trzydziestu krawędziach. W załączniku przesyłam przykładowe rozszerzenie.