0
$\begingroup$

I tried to prove that a simple graph $G$ with at least two vertices has two vertices of the same degree. It's easy to prove that this is true by the pigeonhole principle. If we remove the hypothesis that $G$ is simple can we affirm that $G$ necessarily has two vertices of the same degree? For example, if a $G$ has 3 vertices and between 1,2 there are two edges and between 2,3 only one we have one vertex of degree 2, one of degree 3 and the last of degree 1. Is it correct?

$\endgroup$
0
$\begingroup$

Not necessarily. Consider the graph on 3 vertices $x,y,z$ where there are 2 edges between $x$ and $y$, 1 edge between $x$ and $z$ (and no edges between $y$ and $z$). So $d(x) = 2+1=3$, $d(y) = 2$ and $d(z)=1$.

$\endgroup$
0
$\begingroup$

Your example is correct. If multiple edges between two vertices are allowed, it may not be the case that there are two vertices of the same degree.

$\endgroup$

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.