1
$\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$
3
  • $\begingroup$ By 'loop' you mean that there can be an edge from a vertex to itself? $\endgroup$
    – Bram28
    Jun 6, 2017 at 20:56
  • $\begingroup$ Yes, exactly. :) $\endgroup$
    – HehHeh
    Jun 6, 2017 at 20:57
  • $\begingroup$ OK, then a simple counterexample will do! $\endgroup$
    – Bram28
    Jun 6, 2017 at 21:02

1 Answer 1

3
$\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$
3
  • $\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, 2017 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, 2017 at 21:05
  • $\begingroup$ Okay, thank you very much :) $\endgroup$
    – HehHeh
    Jun 6, 2017 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.