I had to draw a simple graph (undirected, no multiple edges & loops) and the degrees of the vertices were $1, 1, 2, 3, 4, 5, 6$.
I knew the total degree was an even number $(22)$, so the graph must exist. I tried drawing $6$ edges from the highest-degree vertices $(6)$, then chose a random vertex and drew $4$ edges from there (because it already has $1$ edge). I kept doing this for a while and ultimately the graph had $2$ vertices of degree $2$, which was not what I wanted.
Is there a method for drawing simple graphs given the degrees of the graph's vertices?
Best Answer
Such simple graph does not exist. If such $G$ exists, then let $u$, $v$, $a$, $b$ be the vertices in $G$ such that $\deg(u)=5$, $\deg(v)=6$, $\deg(a)=\deg(b)=1$.
Since $G$ is simple and has $7$ vertices, then $a$ and $b$ must be adjacent to $v$. Since $\deg(a)=\deg(b)=1$, $u$ is not adjacent to $a$ and $b$. This implies that $\deg(u)\leq 7-3=4$, since $u$ is not adjacent to $u$ (by fact that $G$ is simple), $a$ and $b$.