Suponha que temos um grafo \(G\) com \(n\) vértices e \(m\) arestas. Se \(G\) possui um emparelhamento máximo com \(k\) arestas, o que se pode afirmar sobre a relação entre \(n\), \(m\) e \(k\)?
a) \(m/2 \leq k \leq n/2\)
b) \(k \leq m/2\)
c) \(k = n\)
d) \(k \leq n/2\)
e) NDA
Ideia original de: Juan David Nieto
Nenhum comentário:
Postar um comentário