# The next difficult graph

We’re slowly adding $\alpha$-properties and $\alpha$-bounds. After adding the property of being almost-edge-KE, the program popped out the following graph, “difficult” with respect to the fledgling theory:

If you remove vertices 5 and 7, you get a KE graph. It can be argued that, if you remove a pair of vertices from a graph G and get a KE graph, then either G has a non-empty KE part (and the problem of calculating independence can be efficiently reduced to that of a smaller graph or, if n=2k+1, alpha=k, and if n=2k, alpha=k-1. So again the program is suggesting how to extend the theory. In this case, the programmed bounds are rather far apart. alpha=3 here, whereas the Cvetkovic upper bound is 5, and the residue lower bound is 2.

Adding this property, we find that the independence number of all graphs through order 8 can be computed efficiently. Here’s the next difficult graph:

It has a degree 2 vertex – which is foldable. And so we know the next property to add.