- Consider a graph $\Gamma$ of order $n \ge 3$, with $n-1$ different degrees. There has to be exactly one number $i$ that is the degree of exactly two vertices. What are the possible values of $i$?
My attempt: The graph has order $n$, so for the degree $k$ of a vertex of this graph we have $0 \le k \le n-1$ (antireflexive!). However the values $0$ and $n-1$ cannot occur at the same time. So the possible values of the occurring degrees are $\{0,\dots,n-2\}$ or (exclusive) $\{1,\dots, n-1\}$. This means that we can always guarantee that $1 \le i \le n-2$, which - I believe - is the answer.
- How many non-isomorphic graphs of order $n$ are there with exactly $n-1$ different degrees?
My attempt: This one is harder. Consider two graphs $\Gamma_1$ and $\Gamma_2$. I know that if 1) $|V(\Gamma_1)| \ne |V(\Gamma_2)|$, 2) $|E(\Gamma_1)| \ne |E(\Gamma_2)|$ or 3) $\exists v \in V(\Gamma_1): \deg_{\Gamma_1}(v) \ne \deg_{\Gamma_2} (\phi(v))$, the two graphs are not isomorphic. Like in the bullet, we know that the possibilities of the value of the vertex degrees are $\{0,\dots,n-2\}$ or $\{1,\dots, n-1\}$.
In both cases there will be $n!$ possible graphs ($n \cdot (n-1) \cdot \dots \cdot 1$), so that makes a total of $2 \cdot n!$. I don't know how to find out whether or not I've included isomorphic graphs in this total.
Thanks a lot!
The sum of the degrees of all the vertices has to be even. If $n$ is odd this will rule out some possible values of $i$. For example, if $n=5$ you could have vertices with degrees $0,1,2,3$ or $1,2,3,4$. The sum of both of these sets is even, so the last vertex must have even degree. It can't be $0$ in the first case because you couldn't have a vertex of degree $3$, so it must be $2$. In the second case you can't have two vertices of degree $4$ because of the one with degree $1$, so again the degree that must be duplicated is $2$. For $n=4$ you can have degrees $0,1,2$, which sums to $3$ so the duplicated degree must be odd and therefore $1$. If you have degrees $1,2,3$ the sum is even and the duplicated degree must be $2$.
I would draw graphs for $n=6$ and $7$ to try and see if you have choices.