A follow-up thought from Ermelinda DeLaVina: “This morning I had this thought for another (maybe slight easier to compute) lower bound for the difficult graph J?`FBo{fdb?.

Let H be the subgraph induced by the non-maximum degree vertices. Then alpha(G) >= Residue(H).

This is another instance of “the corollary sometimes gives a better bound”.

Proof: Let S be any subset of vertices of G, and G[S] the subgraph induced by S. Then alpha(G) >= alpha(G[S]) >= Residue(G[S]).

When S is the set of non-maximum degree vertices, Residue(G) and Residue(G[S]) are non-comparable. To see this take J?`FBo{fdb?, and a large enough complete graph with one edge subdivided, for instance.

It would be interesting if one could find an easily computed set that so that its residue is never worse than residue of the graph.”

In this case, alpha(G[S])=4, which is exactly the independence number of the difficult graph.