Answer to Question #349298 in Discrete Mathematics for nouman

Question

Question 1: Draw a graph with the specified properties or give reason to show that no such graph exists.

i.                    A graph with four vertices of degree 1,1,2 and 3

ii.                  A graph with four vertices of degree 1,1,3 and 3

iii.                 A simple graph with four vertices of degree 1,1,3 and 3

Answer 1

i. We know that sum of degrees of all the vertices is twice the number of edges contained in it, so this sum is even for each graph.

A graph with four vertices of degree 1,1,2 and 3 does not exist because the sum of degrees of all the vertices is odd: 1+1+2+3=7.

ii. A graph with four vertices of degree 1,1,3 and 3:

iii. A simple graph is a graph without loops and multiple edges.

A simple graph with four vertices of degree 1,1,3 and 3 does not exist. We have 4 vertices and two of them of degree 3, so these vertices are adjacent to all the other vertices and the other 2 vertices must have degree at least 2, not 1.