Possible and Impossible Graphs Do the following graphs exist? If so, draw an exa
ID: 3123777 • Letter: P
Question
Possible and Impossible Graphs
Do the following graphs exist? If so, draw an example. If not, give a reason for it.
a) A simple graph with 6 vertices, whose degrees are 2, 2, 2, 3, 4, 4.
b) A simple graph with 8 vertices, whose degrees are 0, 1, 2, 3, 4, 5, 6, 7.
c) A simple graph with 4 vertices, whose degrees are 1, 2, 3, 3.
d) A simple graph with 5 vertices, whose degrees are 2, 3, 4, 4, 4.
e) A simple graph with 4 vertices, whose degrees are 1, 1, 2, 4.
f) A simple digraph with 3 vertices with in-degrees 0, 1, 2 and out-degrees 0, 1, 2.
g) A simple digraph with 3 vertices with in-degrees 1, 1, 1 and out-degrees 1, 1, 1.
h) A simple digraph with 4 vertices with in-degrees 0, 1, 2, 2 and out-degrees 0, 1, 1, 3.
i) A simple digraph with 5 vertices with in-degrees 0, 1, 2, 4, 5 and out-degrees 0, 3, 3, 3, 3.
j) A simple digraph with 4 vertices with in-degrees 0, 1, 1, 2 and out-degrees 0, 1, 1, 1.
Explanation / Answer
(According to Chegg policy, only four subquestions will be answered. Please post the remaining in another question)
Please note, the sum of the degrees of all vertices = 2 * total number of edges.
=> Sum of the degrees of all vertices should be even
a) 2, 2, 2, 3, 4, 4
Their sum is 2 + 2 + 2 + 3 + 4 + 4 = 17
Since the sum is odd, it is not possible to draw the graph.
b) 0, 1, 2, 3, 4, 5, 6, 7
The vertex with greatest degree is 7, so it must have an edge with all other vertices. But there is a vertex with degree 0. This cannot have an edge with any other vertex. So, it is not possible to draw the graph.
c) 1, 2, 3, 3
Sum = 1 + 2 + 3 + 3 = 9
Since the sum is odd, it is not possible to draw the graph.
d) 2, 3, 4, 4, 4
Sum = 2 + 3 + 4 + 4 = 13
Since the sum is odd, it is not possible to draw the graph.