Graf prosty

Definicja

Dla grafu prostego ${\displaystyle G=(V,E)}$, zbiór krawędzi ${\displaystyle E}$ jest skończonym zbiorem dwuelementowych podzbiorów ${\displaystyle V}$ . Równoważnie, możemy powiedzieć, że jest to taki graf ${\displaystyle (V,E,\phi )}$, że ${\displaystyle (\forall e\in E)(|\phi (e)|=2)}$.

Jeśli graf ${\displaystyle G}$ jest prosty o liczbie wierzchołków ${\displaystyle n\geq 1}$ to zachodzą następujące własności:

• Graf ${\displaystyle G}$ jest drzewem, czyli jest spójny i nie ma cykli.
• Graf ${\displaystyle G}$ jest spójny i ma ${\displaystyle n-1}$ krawędzi.
• Graf ${\displaystyle G}$ ma ${\displaystyle n-1}$ krawędzi i nie ma cykli.

Twierdzenie Diraca

Graf prosty ${\displaystyle G}$, takie że ${\displaystyle |V(G)|\geqslant 3}$ oraz ${\displaystyle (\forall v\in V)(\deg(v)\geqslant {\frac {|V(G)|}{2}})}$ jest hamiltonowski.

Twierdzenie Orego

Graf prosty ${\displaystyle G}$, taki że ${\displaystyle |V(G)|\geqslant 2}$ oraz z nierównością ${\displaystyle \deg(v)+\deg(u)\geqslant n}$ zachodzącą dla każdej pary niepołączonych krawędzią wierzchołków posiada cykl Hamiltona.

Izomorfizm

Grafy proste ${\displaystyle (V_{1},E_{1})}$ oraz ${\displaystyle (V_{2},E_{2})}$ są izomorficzne, jeśli istnieje bijekcja ${\displaystyle f:V_{1}\to V_{2}}$ taka, że ${\displaystyle (\forall x,y\in V_{1})(\{x,y\}\in E_{1}\equiv \{f(x),f(y)\}\in E_{2})}$.