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$

2 Answers 2

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .