Let G $=($V$,$E$)$ be a given graph. We have seen that, any maximal independent set for G$2$ dominates G$2$ and lower$-$bounds any dominating set for G in size.

Consider the following greedy algorithm, which computes a dominating set for G$2$ that is minimal is size.

Algorithm $1$ Greedy$-$Algo$-4-$Dominating$-$Set

$1$: U $$V$.$

$2$: while there exists v in U such that U $\backslash \{$v$\}$ still dominates V in G$2$ do

$3$: Remove v from U$.$

$4$: end while

$5$: Output U$.$

Prove or disprove that, the set U output by the greedy algorithm lower$-$bounds the size of the optimal dominating set for any given graph G$.$

Prove or disprove that, the set $\backslash ($ U $\backslash )$ output by the greedy algorithm lower$-$bounds the size of the optimal dominating set for any given graph $\backslash ($ G $\backslash ).$