Na figura seguinte está representada uma
bicoloração dos vértices do grafo
G.
Logo
- G é um grafo bipartido.
- G não tem ciclos hamiltonianos porque
num grafo bipartido todo o ciclo elementar tem comprimento par.
No entanto G tem ordem 9, ímpar.
- o grafo G tem ciclos eulerianos porque
todos os vértices de G têm grau par.
- G tem subgrafos que são árvores,
por exemplo um subgrafo gerado por um par de vértices
adjacentes.