Proving algorithm for removing nodes from a complete graph with two kinds of edges
A complete graph with red and black edges is just an unnecessarily complicated way of describing an arbitrary graph (where black edges correspond to neighbors and red edges to non-neighbors).

Effectively, given a graph $G$ you are looking for a subset of the vertices that is both a clique and a vertex cover.

Restating the problem like this, it is easier to see that your arguments are correct: in a graph with no isolated vertices, if there is more than one connected component (in an undirected graph every connected component is also strongly connected so stating "strongly connected" is redundant) then clearly there is no clique that covers both components.

Let $\Delta$ be the maximum degree of the graph $G=(V,E)$ and let $v$ be a degree-$\Delta$ vertex. Suppose there is a valid solution $S\subseteq V$ that does not contain $v$, then this solution must contain all of $v$'s neighbors. Suppose $S$ can not be extended to a valid solution by adding $v$, then $S$ contains some vertex not adjacent to $v$, thus the graph restricted to $S$ is a clique of size least $\Delta+1$ in which all vertices have degree at least $\Delta$. However, then the graph restricted to $S\cup{v}$ has a vertex of degree at least $\Delta+1$, contradicting that $\Delta$ is the maximum degree. Thus if a valid solution exists then this solution remains valid when adding a maximum-degree vertex.

So the algorithm can be restated in much simpler terms: take all maximum-degree vertices, and check that they are a valid solution.