2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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?> $\endgroup$ – bof May 27 '15 at 8:26
  • $\begingroup$ couldnt you just draw 7 vertices connecting each other? im not sure i follow $\endgroup$ – henryt May 27 '15 at 8:31
  • $\begingroup$ 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. $\endgroup$ – bof May 27 '15 at 8:42
  • $\begingroup$ i think you mis-interpreted my answer :P im also saying a graph with a closed euler trail therefore the statement is wrong :P $\endgroup$ – henryt May 27 '15 at 8:49
  • $\begingroup$ 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?? $\endgroup$ – bof May 27 '15 at 8:58
2
$\begingroup$

You are correct on part (A).

In (B) such a graph is not possible. Because if you look at the vertex that has degree 6 it must be connected with all the other vertices in the graph. But then there is a vertex of degree 5 it will be connected to the degree 6 vertex plus 4 other vertices. But there are two vertices of degree 1 that are already exhausted by the degree 6 vertex hence such a connection is not possible.

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.

$\endgroup$
  • $\begingroup$ for e) where you count the degrees with respect to edges and vertices, is that only for trees or is that for any graph $\endgroup$ – henryt May 27 '15 at 8:33
  • $\begingroup$ or is it that if ANY graph is connected, its automatically a tree? $\endgroup$ – henryt May 27 '15 at 8:35
  • $\begingroup$ I have edited that part. $\endgroup$ – Miz May 27 '15 at 8:39
  • $\begingroup$ Another definition of a tree is a connected graph with no cycles. $\endgroup$ – CPM May 27 '15 at 8:47

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.