5
$\begingroup$

Is it true that for every $n\geq 3$ one can find an undirected grpah, with no loops or double edges, on $n$ vertices such that there are $n-1$ vertices, all with different degrees? (Clearly there can not be $n$ different degrees by the pigeonhole principle).
Thanks for any help.

  • 0
    But then it is trivial :)2012-05-30

2 Answers 2

11

You can induct. Let $G_n$ be such a graph on $n$ vertices; then your pigeonhole argument shows that $G_n$ has either a vertex of degree $n-1$ or a vertex of degree $0$, but not both. Also, its complement $\tilde{G_n}$ is another such graph, which has a vertex of degree $0$ iff $G_n$ does not. So we can suppose without loss of generality that $G_n$ has no vertex of degree $0$. But then the union of $G_n$ with an isolated vertex is such a graph on $n+1$ vertices.

  • 0
    thanks, a very nice proof!2012-05-30
0

If $n$ is odd start with a path of length $2$ otherwise start with a single edge. At each step, add two vertices and connect one of them to all other vertices until you have graph on $n$ vertices and it will have the desired property.