finding tight upper bound of the size of vertex cover
a vertex cover of an undirected graph G = V, E : C º V is a vertex cover
for G if given any u, v ¸ E, at least one of u or v is in C. Prove that
|V | − 1 is a tight upper-bound for the size of a vertex cover.
No comments:
Post a Comment