Prova de grafo simples com vértices de grau 1, 1, 3, 3 §

---

Prove: A existência de um grafo simples de 4 vértices de grau 1, 1, 3, 3 é possível? Explique!

Prova por contradição: suponha por contradição que exista um grafo com 4 vértices e graus 1, 1, 3 e 3. Seja os vértices de .

u --> v
v --> y
u --> x
x --> y
u --> y

Suponha que tenha grau 3, logo existe uma aresta entre e os demais vértices. E o mesmo acontece com . Portanto, só pode ter grau 2 pois uma aresta está ligada a e outra uma aresta está ligado a . O mesmo ocorre com o vértice .

Portanto, por contradição não pode existir tal grafo.

c.q.d.

Referências §

---