The two examples you mention have a very nice generalization but the general counting problem seems hopeless. Let me start with the nice result. It is a fun (and easy) exercise to show that in any simple graph there are at least two vertices with the same degree. Define a $g(n,k,d)$ to be a simple unlabeled graph with $n$ vertices and $n-k+1$ distinct degrees, The degree $d$ taken by exactly $k$ vertices and some other $n-k$ degrees taken once each. Also, let $N(n,k,d)$ be the number of $g(n,k,d)$.
You make two interesting remarks. That $N(4,2,2)=1$ the graph having degrees $1,2,2,3$ (this is true) and that $N(3,2,1)=1$ because of the path $P_3.$ However this number is actually $2$ because the complement (an edge and an isolated vertex) is another example.
It turns out that for each $n \ge 2$ there are exactly two $g(n,2,d)$ : a connected one with $d=\lceil n/2 (n-1)/2 \rceil$ and the complement which is not connected and has $d=\lfloor n/2 (n-1)/2 \rfloor.$
I'm sure that this is well known but didn't find it in a short bit of looking around. The ingredients of an induction proof are the following operations:
- The complement of a $g(n,k,d)$ is a $g(n,k,n-d-1).$
- If an isolated vertex is added to a connected $g(n,k,d)$ then the result is a disconnected $g(n+1,k,d).$ And if the unique isolated vertex of a $g(n+1,k,d)$ is removed, the result is a $g(n,k,d.)$
- If a new vertex is added to a $g(n,k,d)$ (connected or not) and then an edge is drawn to each old vertex, the result is a $g(n+1,k,d+1).$ And if a $g(n+1,k,d+1)$ has a unique vertex of degree $n$, it may be removed to obtain a $g(n,k,d).$
This leaves a few steps to fill in.
Mathscinet gives little information about On graphs having exact two vertices with the same degree. Nor about On graphs having exact three vertices with the same degree.
At the other extreme, the case $k=n$ of graphs regular of degree $d$ is reasonable but not trivial for $d=2.$ (In that it is the number of partitions of a certain type so at least has a name.) For larger $d$ it would be hopeless to get exact numbers for large $n$ . And the general case seems equally difficult. In a few isolated cases an answer might be fairly easy such as $k=n-2$ vertices of degree $1$ (or maybe $n-m$ for small $m$.)
