Ensino Superior ⇒ Grafo Tópico resolvido

[Kssy]

Qual o maior número possível de vértices num grafo com 18 arestas, sabendo que todos os seus vértices tem grau maior ou igual
a 3? Justifique.

[poti]

Eu teria que desenterrar meu caderno de Discreta e procurar na teoria de grafos pra poder te ajudar. Esse exercício não tem a ver com caminhos eulerianos/hamiltonianos ?

Abraço!

[Kssy]

tem sim.

[danmat]

Olá Kssy,

Seja [tex3]G[/tex3] um grafo, tal que [tex3]gr(v)[/tex3] representa o grau de um vértice [tex3]v \in G[/tex3]. Temos que

[tex3]\sum gr(v) = 2 \cdot E[/tex3]

Onde [tex3]E[/tex3] é o número de arestas do grafo [tex3]G[/tex3]. Neste caso:


[tex3]\sum gr(v) = 2 \cdot 18[/tex3]

[tex3]\sum gr(v) = 36[/tex3]

Seja [tex3]n[/tex3] o número de vértices do grafo [tex3]G[/tex3], assim temos que

[tex3]3n \leq \sum gr(v) = 36[/tex3]

[tex3]3n \leq 36[/tex3]

[tex3]n \leq 12[/tex3]

Portanto o número máximo de vértices neste grafo é igual a 12.

Abraços!