grafy mat123: Witam, czy mogę prosić o sprawdzenie mojego toku rozumowania? Wykaż, że w dowolnym grafie rzędu co najmniej dwa istnieją dwa wierzchołki tego samego stopnia. Dowód nie wprost: Zakładamy, że każdy wierzchołek w grafie ma inny stopień. Zatem istnieje taki wierzchołek, który ma stopień 0 oraz taki wierzchołek, który ma stopień n−1. Przy czym n to liczba wierzchołków w grafie. Na podstawie zasady szufladkowania otrzymujemy sprzeczność, ponieważ nie istnieje wierzchołek, który sąsiaduje z każdym innym wierzchołkiem i jednocześnie nie sąsiaduje z żadnym innym. Czy ten dowód jest przeprowadzony poprawnie?

jc: Nie. Na jakiej podstawie zakładasz, że istnieje wierzchołek stopni 0 oraz wierzchołek stopnia n−1?

mat123: No skoro każdy wierzchołek ma inny stopień to spośród wszystkich n wierzchołków musi się taki znaleźć.

jc: o.k. (to pierwsze stwierdzenie też wynika z zasady szufladkowej).

mat123: Czyli podwójne zastosowanie zasady szufladkowej i dowód jest poprawny?

Blee: "Na podstawie zasady szufladkowania otrzymujemy sprzeczność, ponieważ nie istnieje wierzchołek, który sąsiaduje z każdym innym wierzchołkiem i jednocześnie nie sąsiaduje z żadnym innym." <−−− wiem o co Ci chodzi, ale to jest źle napisane. Winno być coś w stylu: "Na podstawie zasady szufladkowania otrzymujemy sprzeczność, ponieważ nie istnieje wierzchołek, który sąsiaduje z każdym innym wierzchołkiem i jednocześnie inny wierzchołek nie sąsiadujący z żadnym."