We just learned about the *magnet reduction *in a new paper by Leveque and de Werra, “Graph transformations preserving the stability number” in DAM 160 (2012). If, for adjacent vertices *a* and *b, *every vertex of N(a)\N(b) is adjacent to every vertex of N(b)\N(a) then this pair of vertices is called a *magnet*. If *G* is the original graph and G’ is the graph formed by removing both vertex *a* together with every edge adjacent to vertex *b* then, it can be argued, alpha(G)=alpha(G’). Since identifying whether a graph has a magnet requires inspection of at most *e* edges and then finding the neighborhoods of the endpoints, this property can be checked efficiently.

In fact, the last difficult graph I?b@fd}^_ has a magnet – and is efficiently reducible. After Patrick added the property “has_magnet” to INP, he ran the program and discovered the next difficult graph I?bbrr[ko.

This graph has order 10, and independence number 4. Lovasz theta correctly predicts alpha, but the best lower bound is 3 – so we need a better lower bound that will predict the independence number of this graph – or we need a new reduction that works for this graph. Intriguingly, this graph has *stable blocks*: for each of the following non-maximum independent sets I, it is the case that . These sets are [0, 1, 2], [0, 1, 3], [0, 2, 3], [1, 2, 3], [1, 2, 4], [1, 3, 4], [2, 3, 4].