What I seek is a formula $F(v,d)=M_v$, where $v$ is the number of vertices in a group and $d\leq v-1$ is the degree that they ALL have to be ($d$-regular graph$^{\dagger}$), which finds the MAXIMUM number of vertices $M_v$ that can be selected in such a way that no two selected vertices share a common edge, i.e., the independent set.$^{\dagger\dagger}$
For example:
$F(3,2)$ would represent
and the maximum number of vertices that can be circled so that no two share an edge would be $1$, so $F(3,2)=1$. Consider now the representations of $F(4,2)$ and $F(4,3)$:
$F(4,2)=2$ and $F(4,3)=1$
Also, notice that for higher $v$, e.g. here, there exists the possibility of multiple types of networks some of which may be disjoint from other vertices in the group. For example, $F(4,1)$ could be represented as
Notes:
I think we can agree that $F(v,v-1)=1$.
$\dagger$ Erick Wong's contribution.
$\dagger\dagger$ Erick Wong's contribution.
Best Answer
This should be a fairly straightforward problem using what we know about graphic degree sequences, but it probably involves analyzing several cases. It turns the exact formula you are looking for was already worked out 40 years ago in Moshe Rosenfeld's thesis. You can find the relevant info (Theorem 1) on p.263 of
M. Rosenfeld, "Independent Sets in Regular Graphs", Israel J. Math. (1964) Vol 2:4, pp.262–272.
The preview link is enough to see the statement of the theorem, which yields
$$F(v,d) = \min\{\lfloor v/2\rfloor, v-d\},$$
except that of course the function is undefined when $v,d$ are both odd. The theorem also gives the precise bounds for the minimum independence number.