teoria grafow maciek: AGH MATEMATYKA STOSOWANA ,GRAFY Wykaz ze jesli graf dwudzielny G (X,Y,E) jest k−regularny, k≥1, to |X|=|Y|. Czy dałby rade ktos rozpisac to w sposob formalny jak być powinno? Ja mam idee zeby zrobic to nwpr. . Czyli: Niech |X|=n zakladamy, ze |X|<|Y|. Wtedy zbior Y musi miec moc conajmniej X+1. Zatem tworzymy z zbioru Y podzbior A o mocy X. Wtedy z zbioru X wtrafia do podzbioru A zbioru Y k*n krawedzi (tyle samo wychodzi z pozdzbioru A do X). Ale istnieja jeszcze wierzcholki w zbiorze Y do ktorych nie poprowadzono zadnej krawedzi (to sa te po za podzbiorem A w zbiorze Y). A wiec z tego wynika ze z X musi wychodzic jeszcze jakas dodatkowa krawedz przez co graf G przestaje byc grafem k−regularnym. A wiec pokazalismy sprzecznosc ze |X|<|Y| a wiec |X|=|Y| móglby ktos to zapisac w sposob symboliczny tak aby ten dowod byl calkowicie poprawny ? pozdrawiam

maciek: moze tak : |X|=n , v₁, v₂ , .... , v_n ∊X Niech |X|<|Y| ⇒ |Y|≥|X|+1 , w₁, w₂,... , w₍n+1) ∊Y wezmy podzbior A⊂Y : |A|=n , oraz w₁,w₂,... , w_n ∊A (podzbior zbioru Y) z X wychodzi kn krawedzi do A ale musi dodatkowo wyjsc jedna do w₍n+1) , bo |X|<|Y| ⇒ ∃ v_i ∊X : deg v_i = k+1 , i∊{1,...,n} , co daje nam sprzecznosc.

maciek: ponawiam, czy ktos cos wie ?