# 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.

## 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 on other sites
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 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 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 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.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 9
• 9
• 11
• 11
• 23
• ### Forum Statistics

• Total Topics
633677
• Total Posts
3013284
×