Answer: set S: unprocessed vertices. set C: vertices in the current component that have received a colour, but whose neighbours we haven't yet checked. set S and set C: no vertex is ever in both sets at the same time. not in set S or in set C: vertices in components that have been fully processed. That is, they are coloured and their neighbours have been checked.
Answer: The worst case is a graph where the nodes can be divided into two sets where each node in one set is connected to every node in the other. (Note: This is called a ``complete bipartite'' graph.)
Proof (your explanation didn't have to be this formal):
When a vertex is placed in C, it is removed from S. This happens exactly once for each vertex v.
Therefore each iteration of the middle loop reduces the number of iterations of the outer loop by 1. Thus, the number of times the guards of the middle and outer loops are tested, combined, is O(n).
So the way to maximize the total number of steps is to maximize the
number of iterations of the inner loop. This happens when all edges
are present in a bipartite graph, so that inner loop always checks
n/2 neighbours, which gives a worst-case running time of O( 
)
for the whole algorithm. (If more edges are present, then the graph
is not bipartite, and a conflict will be found before all vertices
are processed.)
Note: we don't need to prove that all vertices are visited, since this isn't a correctness proof.
Answer: The outermost loop executes only once, since the middle loop processes all the vertices.
Answer: once, since vertices are never placed back in S.
Answer: Once. The insertions happen in the first part of the if-statement, and the guard for that is true only when the current vertex w does not yet have a colour; in that first part, w is given a colour.
Answer: The inner loop is O(n). The middle loop
executes n times, once for each vertex placed in C.
The outer loop executes exactly once (see question 3 above).
So the algorithm
is O( ).
Answer: Since the innermost loop has a removal from
S, and this takes O(n), the running time is increased by an
order of magnitude to O( 
).