MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

4 added 8 characters in body

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

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 nice fun (but simpleand easy) exercise to show that in any simple graph there are at least two vertices with the same degree. You seem Define a $g(n,k,d)$ to be asking for things like "Exactly how many graphs have a simple unlabeled graph with $n=17$ n$vertices of which and$k=11$have n-k+1$ distinct degrees, The degree $d=3$ and the other d$taken by exactly$6$have k$ vertices and some other $6$ n-k$degrees which can taken once each. Also, let$N(n,k,d)$be arbitrary as long as none the number of them are$3$and no g(n,k,d)$.

You make two are interesting remarks. That $N(4,2,2)=1$ the same?"

If 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 question then 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 \rceil$ and the complement which is not connected and has $d=\lfloor n/2 \rfloor.$

I'm sure that this is well known but didn't find it in a few isolated cases short bit of looking around. The ingredients of an answer might be fairly easy such as induction proof are the following operations:

• The complement of a $k=n-2$ vertices 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 degree a$1$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 maybe not) and then an edge is drawn to each old vertex, the result is a $n-m$ for small g(n+1,k,d+1).$And if a$m$.) The 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 totally 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 pretty difficult hopeless to get exact numbers for large $n$ .

The other extreme 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 $k=2$ could be interesting to consider. 1$(or maybe$n-m$for small$m$.) 2 added 61 characters in body It is a nice (but simple) exercise to show that in any simple graph there are at least two vertices with the same degree. You seem to be asking for things like "Exactly how many graphs have$n=17$vertices of which$k=11$have degree$d=3$and the other$6$have some other$6$degrees which can be arbitrary as long as none of them are$3$and no two are the same?" If that is the question then 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$.) The case$k=n$of graphs regular of degree$d$is reasonable but not totally trivial for$d=2.$For larger$d$it would be pretty difficult to get exact numbers. The other extreme of$k=2\$ could be interesting to consider.

1