Graph Theory Question: Finding Equal Degree Vertices in Graphs

[Anro]

Homework Statement

Hello everyone;
This is the problem that I am working on:

(a) - Show that in every graph there are two vertices of the same degree.

(b) - Determine all graphs with exactly one pair of vertices of equal degree.

Homework Equations

None.

The Attempt at a Solution

For part (a) I assumed a graph of order n with the largest possible degree is (n – 1), and the smallest possible degree is zero. Next, I showed that if every vertex in this graph has a different degree than the others, then the vertex with degree (n – 1) will have to be connected to the vertex with degree zero, which is a contradiction.

Part (b) is where I’m stuck; I’ve been looking at graphs with 2, 3, and 4 vertices to see if I can get a certain pattern but I can’t seem to find it. So any help would be appreciated; thanks in advance.

 

[mighty2000]

Hi there,

For part (a), your approach seems sound and your proof is correct. For part (b), let's consider a graph with exactly one pair of vertices of equal degree. This means that all other vertices must have different degrees. Let's label the vertices as follows: the two vertices with equal degree as A and B, and all other vertices as C, D, E, etc.

First, let's consider the case where A and B are not connected. This means that the degrees of A and B must be different from all other vertices, so let's say A has degree n and B has degree m. This means that the degrees of all other vertices must be less than n and m. However, since there are only n-1 vertices (excluding A), there must be at least one vertex with degree less than m, which contradicts our assumption that B has the smallest degree. Therefore, A and B must be connected.

Next, let's consider the case where A and B are connected. This means that their degrees must be the same, so let's say they both have degree n. This means that the degrees of all other vertices must be less than n. However, since there are only n-2 vertices (excluding A and B), there must be at least one vertex with degree less than n, which again contradicts our assumption that A and B have the largest degree. Therefore, there cannot be a graph with exactly one pair of vertices of equal degree.

In conclusion, there are no graphs with exactly one pair of vertices of equal degree. I hope this helps! Let me know if you have any further questions.