b'\n_START_ARTICLE_\nGraf dwudzielny\n_START_SECTION_\nWarunki wystarczaj\xc4\x85ce dla grafu hamiltonowskiego\n_START_PARAGRAPH_\nSformu\xc5\x82owane zosta\xc5\x82o twierdzenie, kt\xc3\xb3re pozwala okre\xc5\x9bli\xc4\x87, czy graf dwudzielny jest grafem hamiltonowskim.\n_START_SECTION_\nSprawdzenie dwudzielno\xc5\x9bci\n_START_PARAGRAPH_\nAby przekona\xc4\x87 si\xc4\x99, czy dany graf jest dwudzielny, wystarczy u\xc5\xbcy\xc4\x87 algorytmu przeszukiwania grafu (BFS lub DFS) i kolorowa\xc4\x87 wierzcho\xc5\x82ki (pocz\xc4\x85tkowo o kolorze neutralnym) na dwa kolory tak, aby przechodzony wierzcho\xc5\x82ek mia\xc5\x82 kolor przeciwny wzgl\xc4\x99dem poprzednika. Je\xc5\x9bli natrafimy na dwa wierzcho\xc5\x82ki o tym samym kolorze po\xc5\x82\xc4\x85czone kraw\xc4\x99dzi\xc4\x85, to graf nie jest dwudzielny. W przeciwnym wypadku graf jest dwudzielny, podzia\xc5\x82 zbioru wierzcho\xc5\x82k\xc3\xb3w na roz\xc5\x82\xc4\x85czne podzbiory wyznaczaj\xc4\x85 ich kolory.'