# Simple graph with 5 vertices with degree sequence (3,3,3,3,4)

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 .

• Do you know about the Havel-Hakimi theorem about graphical sequences? May 28, 2017 at 14:13

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.

• If you want to visualize the graph, it's a basically a square based pyramid. May 28, 2017 at 14:24

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