cykl,grafy Krystek: Niech G=(V,E) bedzie grafem spojnym.|V|=60 a |E|=59 czy w G moze istniec cykl i czy G jest planarne . jak dla mnie G jest planarne gdyz |V|=|E|−1,nwm jak sprawdzic czy może istnieć cykl?

jc: To drzewo, a więc graf planarny i graf bez cykli.

Krystek: a jak to uzasadnić ze to drzewo?

jc: Indukcyjnie? Jeden wierzchołek, zero krawędzi, drzewo. Załóżmy, że tw. jest prawdziwe dla n wierzchołków. Weźmy n+1. Przynajmniej jeden wierzchołek ma stopień jeden. Inaczej mielibyśmy wbrew założeniu co najmniej n+1 krawędzi. Usuńmy taki wierzchołek wraz z krawędzią. Otrzymany graf będzie spełniał założenia dla n, a więc będzie drzewem. Dołączając usuniętą krawędź wraz z wierzchołkiem otrzymamy drzewo. −−− Jakiś dowód na pewno jest w książce Wilsona.