0
$\begingroup$

I have to show that a finite simple graph with more than one vertex has at least two vertices with the same degree. Then, the question is if this is also true for graphs with loops.

My solution:

If G is a simple graph with more than one vertex and $|VG| = n ≥ 2$ we can discuss two different cases:

Case 1: Assume that G is connected. We can not have a vertex of degree $0$ in G, so the set of vertex degrees is a subset of $S = {1, 2, · · · , n − 1}$. Since the graph G has n vertices, by pigeon-hole principle we can find two vertices of the same degree in G.

Case 2: Assume that G is not connected. G has no vertex of degree $n − 1$, so the set of vertex degrees is a subset of $S′ = {0, 1, 2, · · · , n − 2}$. By pigeon-hole principle again, we can find two vertices of the same degree in G.

Now, I have few examples in my head that can prove that we can't say the same for the graphs with loops but how can I explain that?

Thank you.

$\endgroup$
  • $\begingroup$ By 'loop' you mean that there can be an edge from a vertex to itself? $\endgroup$ – Bram28 Jun 6 '17 at 20:56
  • $\begingroup$ Yes, exactly. :) $\endgroup$ – HehHeh Jun 6 '17 at 20:57
  • $\begingroup$ OK, then a simple counterexample will do! $\endgroup$ – Bram28 Jun 6 '17 at 21:02
2
$\begingroup$

If you already have a counterexample, just state it to disprove the claim. For example the graph with adjacency matrix $$ \begin{bmatrix} 0 & 1 \\ 1 & 1 \\ \end{bmatrix}$$

$\endgroup$
  • $\begingroup$ Okay, so I can prove this if there is a graph with both loops and parallel edges. But, I think that the question is what happens if there are only loops. $\endgroup$ – HehHeh Jun 6 '17 at 21:03
  • $\begingroup$ The counterexample I gave has 2 vertices with edges (1,2) and (2,2). It has only loops $\endgroup$ – Akababa Jun 6 '17 at 21:05
  • $\begingroup$ Okay, thank you very much :) $\endgroup$ – HehHeh Jun 6 '17 at 21:06

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.