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!

  • 2
    $\begingroup$ 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. $\endgroup$ – Ross Millikan May 7 '14 at 20:48
  • $\begingroup$ @Ross Doesn't unqualified “graph” mean “simple graph”? $\endgroup$ – MJD May 7 '14 at 20:51
  • $\begingroup$ @MJD: I don't know. If so, that suffices. $\endgroup$ – Ross Millikan May 7 '14 at 21:11

It's hard to give a good hint about this without giving the whole game away, but I'll try:

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

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!)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.