I was solving some questions about simple graphs and I got the following one:
Does there exists a simple graph with five vertices and degrees 3, 3, 3,3,4.?
I tried to sketch such type of graph but I couldn't....So I think such a graph doesn't exists. But how can I explain this....? Thank you .
$\endgroup$ 13 Answers
$\begingroup$If you consider a complete graph of $5$ nodes, then each node has degree $4$. Now remove any edge, then we obtain degree sequence $(3,3,4,4,4)$. Now chose another edge which has no end point common with the previous one. This makes the degree sequence $(3,3,3,3,4)$
I guess this is what you are looking for.
It exists!
Say $v_1,v_2,v_3,v_4,v_5$ be the vertices of the graph, Connect $v_1$ with the other $4$, then connect $v_2$ with $\{v_3,v_4\}$ then connect $v_3$ to $v_5$ then connect $v_4$ to $v_5$.
Your required graph is formed!
Let $G$ be a graph with $V(G)=\{1,2,3,4,5\}$ and $E(G)=\{(1,2),(1,3),(1,4),(1,5),(2,3),(2,4),(3,4),(4,5)\}$. Then $G$ has the desired degree sequence.
Havel-Hakimi also guarantees this sequence is graphical since $$ \begin{align*} &4,3,3,3,3\\ \leftrightarrow&2,2,2,2\\ \leftrightarrow&1,1,2 \end{align*} $$ is the degree sequence of a path of order $3$.
$\endgroup$
