Proof for $O(n 2^n)$ algorithm to find a minimum $K$-coloring of a graph

Question

I have an algorithm for finding a minimum K-coloring using dynamic programming, but I don't have a proof of why it works.

The algorithm is as follows:

• Consider every subset of vertices $S$ in the graph $G$, starting with the empty set
• Associated with each subset $S$ is two values (initially undefined):
  1. $K_S$ -> The minimum number of colors needed to color that subgraph
  2. $O_S$ -> One set of nodes that are colored the same color in that subgraphs optimal coloring
• For each subset of vertices in the graph, there are two possibilities
  1. If that subgraph S has no edges, $K_S = 1$ (or $0$ if $S$ is the empty set) and $O_S = S$.
  2. If there are some edges in that subgraph, then for each vertex V in S
     1. We try removing that vertex $V$ from $S$
     2. $T = S - V$
     3. $X = 1 + K_{(S - O_T)}$
     4. If $X$ is better than the current $K_S$, then set $K_S = X$ and $O_S = O_T$

After performing the above for each subset in the graph $G$, then $K_G$ is the minimum number of colors.

I would like to know why it is sufficient to consider only the subsets with one vertex removed rather than all possible subsets of that subset $S$.

There is a chance that this algorithm does not work for all graphs, but it has been tested thoroughly on graphs with up to 17 vertices.

Here is my exact java code if that helps anyone. I represent a set of nodes with a single integer, abusing the binary nature of integers in computers so that taking set differences or checking for overlaps is very easy.

    private static int[] solveKColoring(int n, int[] adjLists) {
        int[] optimalSet = new int[1 << n];
        int[] subsetK = new int[1 << n];
        // Overall -> O(n * 2^n)
        for (int set = 0; set < (1 << n); set++) { // O(2^n)
            if (isIndependent(set, adjLists)) { // O(size of set)
                optimalSet[set] = set;
                subsetK[set] = (set == 0? 0 : 1);
            } else {
                int bestK = Integer.MAX_VALUE;
                int bestSet = 0;
                int setCopy = set;
                while (setCopy != 0) { // O(size of set)
                    int b = Integer.lowestOneBit(setCopy);
                    setCopy -= b;
                    int subSet = optimalSet[set - b];
                    int k = subsetK[subSet] + subsetK[set - subSet];
                    if (k < bestK) {
                        bestK = k;
                        bestSet = subSet;
                    }
                }
                optimalSet[set] = bestSet;
                subsetK[set] = bestK;
            }
        }
        return optimalSet;
    }

    private static boolean isIndependent(int set, int[] adjLists) {
        int setCopy = set;
        while (setCopy != 0) {
            int b = Integer.lowestOneBit(setCopy);
            setCopy -= b;
            if ((set & adjLists[Integer.numberOfTrailingZeros(b)]) != 0) {
                return false;
            }
        }
        return true;
    }