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!
It's hard to give a good hint about this without giving the whole game away, but I'll try:
I suppose you've tried drawing a graph where all vertices had different degree. What went wrong? (If you haven't tried, then the hint is: try!)