1
$\begingroup$

enter image description here

I think that this graph exists because the Handshaking Lemma says that the sum of the vertex degrees must be an even number. The sum of the vertices is, $1 + 2+3+4+4 = 14$ . I know that a simple graph is a graph with no loops or multiple edges. I am confused on why this graph does not exist.

$\endgroup$
1
  • 2
    $\begingroup$ If a graph exists, it's degree sequence follows the handshaking lemma. That doesn't necessarily mean that if a degree sequence follows the handshaking lemma, the graph must exist. $\endgroup$
    – Franklin Pezzuti Dyer
    Apr 21, 2017 at 22:53

1 Answer 1

Reset to default
4
$\begingroup$

You have 5 vertices, and two of them have degree 4, which means that both of them are connected to every other vertex, meaning that every vertex must have a degree of at least 2. So, you cannot have one with degree 1.

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