Grafy planarne

[Akiro]

Czy można 10 miast połączyć nieprzecinającymi się drogami, tak aby z każdego miasta wychodziło
5 dróg prowadzących do 5 innych miast?

Tu chodzi o to, żeby skorzystać ze wzoru sprawdzającego planarność, że \(\displaystyle{ W-K+S=2}\)?

W takim razie:
\(\displaystyle{ W=10, K=5^{10}}\) i teraz nie wiem za bardzo jak policzyć liczbę ścian.

W ogóle, czy mój tok rozumowania jest poprawny?

[dvrx47]

Z tego co pamiętam to graf który jest planarny spełnia to równanie, ale nie każdy graf który spełnia to równanie jest planarny (implikacja w jedną stronę) - czyli ten tok rozumowania jest niepoprawny. Na Twoim miejscu pobawiłbym się Twierdzeniem Kuratowskiego (w wersji o minorach grafu).