Page 1 of 1
4. (a) Suppose that the greedy algorithm uses k colors on a graph G. Prove that G must have at least 1+ 2+ ... + (k-1) =
Posted: Wed May 11, 2022 10:05 pm
by answerhappygod
- 4 A Suppose That The Greedy Algorithm Uses K Colors On A Graph G Prove That G Must Have At Least 1 2 K 1 1 (14.35 KiB) Viewed 29 times
4. (a) Suppose that the greedy algorithm uses k colors on a graph G. Prove that G must have at least 1+ 2+ ... + (k-1) = (2) edges. (Hint: whenever a color other than color 1 is used, there are some edges that have to exist to cause this.) (b) Prove that if G has m edges, then (G) <1+ 2m.