Consider an un-directed simple graph $G$.
Define a “tinge” on graph $G$ to be a mapping from $V(G)$ to $\{$“red”, “black”$\}$ Given a graph $G$ and a tinge $T$, we say that the black graph of $G$ given $T$ is graph G with all red nodes removed, and all edges incident to red nodes removed. Define a maximal tinge on graph $G$ to be a tinge, $T$, such that the number of components in the black graph is maximized. In the pictures below, a tinge is shown, and so is the resulting black graph, but the tinge is not maximal.
Prove that for every maximum independent set of vertices in G, if you color the vertices in the independent set black and nodes outside of the set white, then the resulting tinge is maximal.
Attempted Answer:
Suppose we have a tinge $T$ on graph $G$. Let $C$ be a component of the black graph having 2 or more verticies. If we remove a vertex from component $C$, then the number of components in the black graph either stays the same, or goes up. In other words, for any tinge $T$ there exists a tinge $T^{\prime}$ such that every component in the black graph of $T^{\prime}$ contains exactly one node. Thus, for any tinge, there exists an independent set of vertices which gives us the same score. If we want a maximal tinge, we simple use a maximal independent set.
In other words, you want to show that a graph $G$ has an induced subgraph with $m$ vertices and no edges if and only if it has an induced subgraph with $m$ connected components.
One direction is obvious: if a graph has no edges, then each vertex is a connected component.
For the converse observe that, if $H$ is an induced subgraph of $G$ with $m$ connected components, then by choosing one vertex from each component we get an induced subgraph with $m$ vertices and no edges.