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?
2026-04-06 17:13:09.1775495589
Could a non simple graph have at least two vertices of the same degree?
87 Views Asked by Bumbble Comm https://math.techqa.club/user/bumbble-comm/detail At
2
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$.