I've just been introduced to graph theory in my discrete math class and I would like to see if my work and understanding of the topic is correct. Since there are many different terms and terminology in graph theory, the terminology that we agreed upon in class is that vertices are nodes and that an edge is an arc. Now then, on to the problem


Draw a simple graph with three vertices A, B, and C such that

A) deg(A) = deg(B) = 1

B) deg(A) = deg(B) = deg(C) = 1


Part A: In part A, both A and B have a degree of 1, thus both are connected to each other while C has a degree of zero. The graph could look something like this:

enter image description here

Part B: This where I'm stuck. My answer would be that it is impossible to draw a simple graph with three vertices, each with one degree, because as soon as you, say for example, connect A to B, then either A or B is going to have to connect to C and vice of versa. Thus making either A or B degree of 2 which is not what the question was asking.

  • 1
    $\begingroup$ Yes. It is impossible and your reasoning is correct. $\endgroup$ – ZeroXLR Jul 25 '15 at 21:32

You can not do it. The sum of the degrees need to be an even number! Can you prove this?


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.