3
$\begingroup$

I want to prove this claim using contradiction:

Let $G$ be a simple graph with $n$ vertices. Prove by contradiction that $G$ has two vertices having the same degree (Consider the vertex of smallest degree and vertex of largest degree).

I think I know where to start. The vertex of the largest degree is $n-1$ in this graph and the smallest is 1. How can I use contradiction to prove the statement above? I studied the proof of this using pigeonhole but I wanna use contradiction this time.

$\endgroup$
7
$\begingroup$

Suppose such a graph existed. Each vertex in the graph can have a degree from 0 to $n-1$ (simple graphs do not forbid a degree-0 vertex, connected graphs do). Since this range spans $n$ values in total and each vertex degree is different, the degrees are distributed one-per-vertex. In particular, there must exist a vertex with degree $n-1$ and one with degree 0.

Now note that the degree-$n-1$ vertex is connected to all other vertices because the graph is simple, including the degree-0 vertex. But the latter is not connected to any vertex, and this induces the contradiction.

Therefore, two vertices in the graph must have the same degree.

$\endgroup$
  • $\begingroup$ Beat me to it! +1 $\endgroup$ – Draconis Mar 14 '18 at 0:38
1
$\begingroup$

It would really be the same argument turned around a bit. Assume $G$ is a simple graph on $n$ vertices with all vertices having a different degree. The maximum degree of a vertex is $n-1$, so there must be a vertex of degree $0$. If there is a vertex of degree $0$, it is not a simple graph.

$\endgroup$
0
$\begingroup$

Take a graph $G$ where all vertices have distinct degrees. So, $$d(1)<d(2)<\cdots<d(n),$$ and $$d(1)>0, d(2)>d(1)>0, \ldots, d(n)>d(n-1)>\ldots>0.$$

Hence we have just one vertex of degree $\geq n-1$.

However, in a simple graph with $n$ vertices a vertex can have a maximum degree of $n-1$. So, $d(n)=d(n-1)$. So, our assumption of having all degrees different was wrong and we have a contradiction.

So, in a simple graph $G$, we must have at least $2$ vertices of the same degree.

$\endgroup$
  • $\begingroup$ Welcome to Math.SE! Please format you post using MathJax. This page should give you a start at learning how to typeset mathematics here so that your posts say what you want them to, and also look good. $\endgroup$ – Brian Mar 16 at 16:46
  • $\begingroup$ I'm confused about why you have $d(1)>0$. Could you explain further? $\endgroup$ – Mauve Mar 16 at 17:04
  • $\begingroup$ We are showing that we want two vertices of the same degree. So, why would we bother to have d(1) = 0 if we are in a simple graph? I think we can just say that we are considering graphs with at least one edge because in a graph of just one vertex this will never apply. $\endgroup$ – user654759 Mar 17 at 10:38
  • $\begingroup$ There are graphs with at least one edge that also have isolated vertices: for example, consider the graph $•\phantom{==} •—•—• \phantom{==} • \phantom{==} •—•$. So you cannot just omit the 0-degree case. $\endgroup$ – Mauve Mar 17 at 17:09

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.