Counting Special Graphs 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$.
 A: You are looking for the enumeration of graphs with prescribed degree sequence. This is the subject of
Bender, E. A. and Canfield, E. R. (1978). The asymptotic number of labeled graphs with given degree sequences. J. Combinatorial Theory Ser. A 24, 3, 296–307.
McKay, B. D. and Wormald, N. C. (1990a). Asymptotic enumeration by degree sequence of graphs of high degree. European J. Combin. 11, 6, 565–580.
McKay, B. D. and Wormald, N. C. (1991). Asymptotic enumeration by degree sequence of graphs with degrees $o(n^{1/2}).$
These give asymptotic formulas. A numerical method for computing an estimate of the number of graphs with fixed (smallish) $n$ and a given degree sequence is given in:
http://www.people.fas.harvard.edu/~blitz/BlitzsteinDiaconisGraphAlgorithm.pdf
A: 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. 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$.) 
