Rozwiązanie:
Niech G = (V

1

, E

1

, V

2

) będzie grafem dwudzielnym (w którym

zbiór
wierzchołków jest podzielony na V

1

, i V

2

" a każda krawędź łączy

element należący do V2)
Rozważmy w grafie G cykl

v

1

,v

2

,v

3

…..,v

n

-1, v

n-1

, v

1.

Załóżmy na przykład, że v

1

V

1.

Wówczas istnienie krawędzi v

1

v

2

zapewnia, że v

2

V

2

podobnie v

3

V

1

Tak więc mamy:

v

1

v

2

v

2

… v

n-1

v

n

v

1

V

1

V

2

V

1

V

1,

V

1,

V

1

co oczywiście implikuje, że n jest parzyste.

 

*

Pokazać że w grafie dwudzielnym każdy
cykl składa się z parzystej liczby krawędzi.

*

Przykład

*

Twierdzenie: 
Graf jest dwudzielny wtedy i tylko wtedy, gdy nie zawiera cykli mających nieparzystą
liczbę krawędzi. 

*

Dowód: 
(=>)Jeżeli graf jest dwudzielny,  to jak zaobserwowaliśmy powyżej, nie może mieć
„nieparzystych”cykli.

Ten graf zawiera nieparzysty

cykl:

Powyższy rezultat stwierdza że

nie jest on dwudzielny

Tutaj nie ma cyklów nieparzystych :
graf ten jest dwudzielny