Could a non simple graph have at least two vertices of the same degree?

87 Views Asked by At

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?

2

There are 2 best solutions below

0
On

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$.

0
On

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.