-1
$\begingroup$

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$
1
  • 1
    $\begingroup$ Do you know about the Havel-Hakimi theorem about graphical sequences? $\endgroup$
    – Laars Helenius
    Commented May 28, 2017 at 14:13

3 Answers 3

Reset to default
4
$\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.

$\endgroup$
1
  • $\begingroup$ If you want to visualize the graph, it's a basically a square based pyramid. $\endgroup$
    – Josh B.
    Commented May 28, 2017 at 14:24
2
$\begingroup$

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!

enter image description here

$\endgroup$
1
$\begingroup$

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$

You must log in to answer this question.

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