Do the following graphs exist? If so, draw an example. If not, give a reason. a)
ID: 3111073 • Letter: D
Question
Do the following graphs exist? If so, draw an example. If not, give a reason. 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 are1, 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
2.RESULT (i) :
For a given sequence to be graphic,we must have the number of odd degree vertices to be even.
a) Given degree sequence of 6 vertices is (2,2,2,3,4,4)
Here only one odd degree vertex (which is 3) exist . From the result (i) ,no graph exist with this sequence .
Hence the given degree sequence is not graphic.
b) Given degree sequence of 8 vertices is (0,1,2,3,4,5,6,7)
From the result (i) the number of odd degree vertices is 4 , even. But still it is not graphic because a zero degree vertex and seven degree vetex cannot come together in an 8 vertex graph.If a vertex is of degree 7 , it must be adjacent to 7 other vertices , then it is not possible for one vertex to have degree 0.
Hence the given degree sequence is not graphic.
c) Given degree sequence of graph is (1,2,3,3)
From result (i) ,in the given degree sequence number of odd degree vertices is 3,which is odd ,not an even number.
Hence the given degree sequence is not graphic .
d) Given degree sequence of graph is (2,3,4,4,4)
From result (i) ,in the given degree sequence number of odd degree vertices is 1, which is odd , not an even number.
Hence given degree sequence is not graphic.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.