| Jeśli G jest grafem dwudzielny, to każdy cykl w G ma długość parzystą.
• Zbiorem rozspajającym grafu spójnego G nazywamy zbiór krawędzi, których usunięcie spowoduje, że graf G przestanie być spójny.
• Rozcięcie jest to zbiór rozspajający, którego żaden pozdbiór właściwy nie jest już zbiorę rozspajającym.
• Jeśli rozcięcie składa się z jednej krawędzi e, to tę krawędź nazyway mostem.
i Jeśli graf G jest spójny, to jego spójnością krawędziową A(G) nazyway liczbę-krawędzi należących do najmniej-licznego rozcięcia grafu G.
• Zbiorem rozdzielający grafu spójnego G nazyway zbiór wierzchołków których usunięcie powoduje, że ten graf przestaje być spójny.
• Graf spójny G nazywamy grafem eulerowskim, jeśli istnieje w nim cykl Eulera.
• Graf spójny G który nie jest grafem Eulera, nazwiemy grafem pół-eulerowskim, jeśli zawiera drogę Eulera.
Twierdzenie Eulera, 1736 Graf spójny G jest grafem eulerowskim wtedy i tylko wtedy, gdy stopień
każdego wierzchołka grafu G jest liczbą parzystą.
Twierdzenie Graf spójny jest grafem półeulerowski wtedy i tylko wtedy, gdy a dokładnie dwa wierzchołki stopnia nieparzystego.
I Graf spójny mający cykl Hamiltona nazywamy Hamiltonowskim.
• Graf spójny który nie jest hamiltonowski nazywamy pólhamiltonowski jeśli zawiera ścieżkę Hamiltona.
Twierdzenie Orego, 1960 Jeśli graf prosty G ma n wierzchołków (gdzie n > 3) oraz
deg(v) + deg(w) > n
dla każdej pary wierzchołków niesąsiednich v i w, to graf G jest hamiltonowski.
Twierdzenie Diraca, 1952 Jeśli w grafie prostym G, który a n wierzchołków (gdzie n > 3), deg(v) > n/2 dal każdego wierzchołka v, to graf G jest hamiltonowski.
1