2
$\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
    Commented Jun 6, 2017 at 20:56
  • $\begingroup$ Yes, exactly. :) $\endgroup$
    – HehHeh
    Commented Jun 6, 2017 at 20:57
  • $\begingroup$ OK, then a simple counterexample will do! $\endgroup$
    – Bram28
    Commented 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
    Commented 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
    Commented Jun 6, 2017 at 21:05
  • $\begingroup$ Okay, thank you very much :) $\endgroup$
    – HehHeh
    Commented Jun 6, 2017 at 21:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .