Do we have any formula for counting the number of graphs with $n$ vertices, that has exactly $k$ vertices with degree $d$ and the other vertices have different and disjoint degrees?
(Different and disjoint are the same, $d\_1$ is different or disjoint rather than $d\_2$, iff $d\_1\neq‎ d\_2$.)


For example, for $n=3, k=2, d=1$, we only have one graph($P\_3$) with this property.
Also, for $n=4, k=2, d=2$, we have the only graph with degree sequence $1, 2, 2, 3$.



Counting Special Graphs
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-1)/2 \rceil$ and the complement which is not connected and has $d=\lfloor (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.](http://www.ams.org/mathscinet-getitem?mr=1637710) Nor about [On graphs having exact three vertices with the same degree.](http://www.ams.org/mathscinet-getitem?mr=1718414) 


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$.) 


