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?
17 gru 18:35
jc: Nie. Na jakiej podstawie zakładasz, że istnieje wierzchołek stopni 0 oraz wierzchołek stopnia n−1?
17 gru 20:21
mat123: No skoro każdy wierzchołek ma inny stopień to spośród wszystkich n wierzchołków musi się taki znaleźć.
18 gru 18:00
jc: o.k. (to pierwsze stwierdzenie też wynika z zasady szufladkowej).
18 gru 18:06
mat123: Czyli podwójne zastosowanie zasady szufladkowej i dowód jest poprawny?
18 gru 18:09
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."
18 gru 18:56