0
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

$\endgroup$
2
$\begingroup$

As Paul points out, this doesn't correspond to a simple graph. Starting with the degree-$6$ node, we can draw edges , but then we fail trying to find enough edges for the degree-$5$ node:

enter image description here

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