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.
a solution to a graph question
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.
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?
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement