# Find a graph with at least two vertices and no self-loops in which all vertices have different degrees

I am an high-school senior interested in Graph Theory, on a web forum a CS teacher teased me with ("an easy but non-trivial") a terrific Graph Theory problem:

Find a graph with at least two vertices and no self-loops in which all vertices have different degrees, or prove that no such graphs exist.

The problem is that I can't find a way to prove my conjecture (which state that such graph don't exist). I tried to reformulate the problem into the following statement, that looks much simpler to me

Prove that in any graph with at least two vertices and no self-loops there is two vertices of the same degree

As of today, I also thought about showing that the graph can't be finite because there is no "equilibrium state" (I don't know if it makes sense in English) were all edges/vertices are compensating each other and satisfying the constraint of the problem.

I am afraid of searching the web, because I don't want to be spoiled the solution by Proof-wiki or some forum, it would be infuriating since I find the problem super fun!

I suspect that I may lack the mathematical maturity to solve it or the knowledge since I (sadly) discovered Graph theory two weeks ago, I only know the very basics of GT (Chapter 6 and 7.1 of Mathematics for Computer Science by Eric Lehmand and Tom Leigthon).

This is probably a good thing to try out such problem without being comfortable with Graph Theory proofs because I could come up with a creative way of solving it but that's also kind of a torture since I feel somewhat stuck right now, exterior help would be appreciated.

Could you please give me hints/ideas to explore?

Please do not disclose too much information (like "use induction on X", "that's trivial, just use theorem X")!

PS: Sorry for any grammar faults!

Thanks a lot!

• I think you need some more conditions on the graph. As the problem is stated, I can find such a graph with three vertices-draw two edges between A and B, then an edge from A to C. I think the problem wants to rule this out. – Ross Millikan May 7 '14 at 20:48
• @Ross Doesn't unqualified “graph” mean “simple graph”? – MJD May 7 '14 at 20:51
• @MJD: I don't know. If so, that suffices. – Ross Millikan May 7 '14 at 21:11

Let $G$ be a connected graph with $n$ vertices. What are the possible degrees of vertices of $G$?