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
Best Answer
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.