# Graph Theory and vertices

For each of the graphs described below, state whether or not such a graph exists. For those that do exist, draw an example of such a graph. For those that do not exist, explain why they do not exist.

(a) A simple graph with 7 vertices with degrees 4, 3, 3, 3, 3, 2, 1 Answer: 19 degrees therefore doesnt exist, the degrees must be even.

(b) A simple graph with 7 vertices with degrees 6, 5, 3, 3, 3, 1, 1 that is not connected.

(c) A simple graph with 7 vertices with degrees 2, 2, 2, 2, 2, 2, 2 that contains no closed Euler trail.

Answer Theorem: you cant have a vertex with a degree of 2 if it isnt connecting another vertex therefore all vertices must connect atleast one other therefore a euler trail will exist.

(d) A simple graph with 8 vertices with degrees 4, 3, 2, 1, 1, 1, 1, 1 that is a tree.

Exists , just drew this one out

(e) A simple graph with 8 vertices with degrees 3, 2, 2, 1, 1, 1, 1, 1 that is connected.

this must contain 14 degrees rather contains 12

While i understand the concept Im not sure if my explanation is sufficient or right

• Your answer to (c) is wrong. Can you draw a simple graph with 3 vertices with degrees 2, 2, 2? OK, now can you draw a simple graph with 4 vertices with degrees 2, 2, 2, 2? OK, now put the two drawings side by side. Do you see 7 vertices with degrees 2, 2, 2, 2, 2, 2, 2? Can you draw a closed Euler trail?> – bof May 27 '15 at 8:26
• couldnt you just draw 7 vertices connecting each other? im not sure i follow – henryt May 27 '15 at 8:31
• Sure, you can draw "7 vertices connecting each other", but that's not what problem (c) asks for. It asks you if you can draw a graph with 7 vertices, all of degree 2, which contains no closed Euler trail. And I just showed you how to draw one. – bof May 27 '15 at 8:42
• i think you mis-interpreted my answer :P im also saying a graph with a closed euler trail therefore the statement is wrong :P – henryt May 27 '15 at 8:49
• You lost me. Part (c) asks, does there exist a simple graph with 7 vertices and degrees 2,2,2,2,2,2,2 that contains no closed Euler trail. I showed you how to draw a simple graph with 7 vertices and degrees 2,2,2,2,2,2,2 that contains no closed Euler trail. What statement is wrong?? – bof May 27 '15 at 8:58

For part (C) such a graph is possible. As an example you have $C_3 \cup C_4$.
For part (E) your judgement is right for such a graph of order 8 to be connected it must at least have 7 edges $\implies$ the sum of degrees of vertices must be at least 14.