Counting vertex covers of size ((r+1)/2) +1 for an odd hole of size r We know that for an odd hole of size r, its minimum vertex cover size = OPT = (r+1)/2. Furthermore, there are r such minimum vertex covers. Was curious to know how many vertex covers exist of size OPT + 1.

For convenience, let $r = 2k+1$. Then we are looking for a vertex cover of $C_{2k+1}$ of size $k+2$.

Let the "structure" of a vertex cover with a specified starting vertex denote the sequence of distances between adjacent vertices. These distances must be either $1$ or $2$ because we have a vertex cover; there are $k+2$ distances, and they add up to $2k+1$. If all $k+2$ distances were $2$, we'd get $2k+4$; so exactly $3$ distances must be $1$, instead. The number of ways to choose which distances are $1$ is $\binom{k+2}{3}$.

Given the structure of a vertex cover, there are $2k+1$ ways to choose which vertex is the starting vertex, but there are also $k+2$ ways to mark a starting vertex on any given vertex cover. So the number of vertex covers is $\frac{2k+1}{k+2}\binom{k+2}{3}$, or $\frac{r^3-r}{12}$.

The answer is polynomial, not exponential, so there is no deep insight to find.