Jump to content
  • Advertisement
Sign in to follow this  
sheep19

a solution to a graph question

This topic is 2529 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am trying to solve a problem in graph theory:

(*) Prove that in a simple graph with at least two vertices there must be at least two vertices with the same degree.

(**) I will prove this using a proof by contradiction. Suppose that the above statement is false. So there may not be at least two vertices with the same degree => all vertices have a unique degree different than all other vertices

Let G = (V, E), where |V| = n (n vertices)

The vertices are {V1, V2, V3, ..., Vn}

The maximum degree of a vertex is n-1, because:
a) no loops are allowed, as this is a simple graph (so no n degree is allowed)
b) it can't be greater than n because there are n vertices :) (and n is not allowed, so it's n-1)

Let's start from Vn to V1 and assign a unique degree to each vertex.
So:
deg(Vn) = n - 1 (all other vertices)
deg(Vn-1) = n - 2
...
deg(V1) = 0

There is a contradiction here. Vertex Vn connects to all other n-1 vertices where V1 is an isolated vertex.
Thus, we reject the hypothesis (**) and accept (*).
---------------------------------------------------------------------------
Is the above proof correct?

Thank you.

Share this post


Link to post
Share on other sites
Advertisement
I think that your proof is basically correct; however, you should be clearer in your argument that the maximum degree of a vertex in a simple graph is n-1. A simple graph isn't just a graph doesn't have self-loops; it also doesn't have multiple edges between two nodes. With multiple edges you can easily construct a graph that doesn't satisfy the property we're trying to prove. For example, G = {V,E} where V = {A,B,C} and E = { A<->B, A<->B, B<->C }, here degree(A) = 2, degree(B) = 3, and degree(C) = 1 but you can't have vertex like B without multiple edges.

Share this post


Link to post
Share on other sites
Thanks for you reply. I didn't even talk about multiple edges because they don't exist in a simple graph. Was it a necessary thing to do?

Share this post


Link to post
Share on other sites
Not sure what you are asking re: Was it a necessary thing to do,...

Just to clarify your statement that "the maximum degree of a vertex in a simple graph is n-1" is correct, so there's nothing wrong with the proof. I was just suggesting that in writing up the proof that you be specific about the fact that both properties of a simple graph are necessay to make this statement correct.

Share this post


Link to post
Share on other sites
I was just suggesting that in writing up the proof that you be specific about the fact that both properties of a simple graph are necessay to make this statement correct.

Ok, I undestand now. Thank you.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!