# Does any graph based optimization problem, which have a greedy algorithm, has guarantee that there exist an order which give the optimum

There exist greedy algorithms for vertex coloring like optimization problems. We know that for graph coloring, there is an order of vertices for which greedy coloring produces the optimum results. Is it true for any problem on graph which has such a greedy algorithm.

• I don't understand your question. What do you mean by "problem has a greedy algorithm"? I suspect that, if you define what you mean, then the answer to your question is trivial "yes", simply by definition.
– user114966
Mar 21, 2021 at 2:35
• I think you get the right meaning of the question. I just want to get the logic behind the "yes". Mar 21, 2021 at 6:54

Take for example Independent Set. The simplest strategy imaginable for finding an independent set is to fix some ordering $$(v_1,\ldots,v_n)$$ on the vertices of your graph $$G$$, putting vertex $$v_i$$ into your independent set $$I$$ if it has no neighbors among the vertices that have been put into $$I$$ so far. This always leads to a maximal independent set, and it's easy to see that every maximal independent set (including those of maximum size) can be generated this way, by just taking an ordering where evey vertex in the set comes before every vertex not in the set.