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