graf prosty

olkab · Post autor: **olkab** » 3 cze 2009, o 20:33

Udowodnić,że graf prosty o co najmiej dwóch wierzchołkach zawsze ma przynajmniej dwa wierzchołki tego samego stopnia.
Wydaje mi się ze mozna zrobic to przez sprzecznosc,czyli przypuscic,ze istnieje taki graf,w którym każdy wierzchołek ma inny stopien,ale dalej niewiem jak to zrobic.

dzieki

miodzio1988 · Post autor: **miodzio1988** » 3 cze 2009, o 22:41

olkab pisze:Udowodnić,że graf prosty o co najmiej dwóch wierzchołkach zawsze ma przynajmniej dwa wierzchołki tego samego stopnia.
Wydaje mi się ze mozna zrobic to przez sprzecznosc,czyli przypuscic,ze istnieje taki graf,w którym każdy wierzchołek ma inny stopien,ale dalej niewiem jak to zrobic.

dzieki

Dobrze kombinujesz
Przypuscmy, że kazdy wierzchołek naszego grafu ma inny stopien. Jest zatem taki wierzchołek, który ma stopień 0 i taki, który ma stopien \(\displaystyle{ n-1}\)(n to liczba wierzchołkow grafu G) No i mamy sprzecznosc Bo jest wierzchołek, który sąsiaduje z kazdym innym wierzchołkiem i taki wierzchołek, który nie sąsiaduje z żadnym innym)

olkab · Post autor: **olkab** » 4 cze 2009, o 19:18

Dziekuje
Mam jeszcze pytanie:Czy grafy o identycznej liczbie krawedzi,wierzcholkow,wierzcholkow wiszacych i identycznych ciągach stopni są izomorficzne ?

miodzio1988 · Post autor: **miodzio1988** » 5 cze 2009, o 01:54

Jak definiujesz wierzchołek wiszący ?

olkab · Post autor: **olkab** » 5 cze 2009, o 05:11

Wierzchołek stopnia 1

miodzio1988 · Post autor: **miodzio1988** » 5 cze 2009, o 17:58

Wydaję mi się, że tak , ale ręki sobie nie dam uciąć (wsrod drzew poszukaj kontrprzykładu)