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.
A graph with almost all degrees different
5
$\begingroup$
graph-theory
-
0But then it is trivial :) – 2012-05-30
2 Answers
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.
-
0thanks, 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.