11. Rozcieciem grafu G = (V,E) nazywamy dowolny pozdbiór E0 zbioru E taki, ze dla dowolnego
zbioru X zawartego w P(E0) {E0} graf G0 = (V,E X) jest grafem spójnym. Udowodnij, ze jezeli
w grafie istnieja dwa rózne rozciecia zawierajace ta sama krawedz, to istnieje takze rozciecie nie
zawierajace owej krawedzi.
20. Udowodnij, ze na dowolnej planszy szachowej rozmiaru n × n, gdzie n jest liczba nieparzysta, nie
istnieje cykl hamiltona dla konika szachowego taki, ze konik odwiedza wszystkie pola szachownicy.
23. Graf prosty G = (V,E), gdzie X(G) = k i X(G) jest liczba chromatyczna grafu, nazywamy krytycznym,
jezeli usuniecie dowolnego wierzchołka grafu G (wraz z krawedziami z nim incydentymi) prowadzi do grafu G0 = (V 0,E0) takiego, ze X(G0) ¡ k.
(e) udowodnij, ze jezli graf G jest k-krytyczny, to kazdy wierzchołek grafu ma stopien nie mniejszy
niz k − 1.
26. Drzewem wywazonym nazywamy drzewo binarne z wyróznionym wierzchołkiem korzeniem, w którym
dla kazdego wierzchołka prawda jest, ze róznica wysokosci jego lewego i prawego poddrzewa wynosi −1, 0 albo 1. Kolejno: (b) wyznacz minimalna liczbe wierzchołków drzewa wywazonego wysokosci h.