Draw a graph with five vertices having degrees 2 2 3 4 4 or

Draw a graph with five vertices having degrees 2, 2, 3, 4, 4 ; or explain why such graph does not exist.

Solution

A directed graph is possible with given out degrees.

adacanc matrix is as follows:

V1

V2

V3

V4

V5

V1

0

1

1

0

0

V2

1

0

0

1

0

V3

1

1

0

1

0

V4

1

1

1

0

1

V5

1

1

1

1

0

but undirected graph is not possible.

vertex 1 can be connected to vertex 4 and 5, making degree of vertex1=2

vertex 2 can be connected to vertex 4 and 5 making degrree of vertex 2=2,

vertex 3 can be connected to vertex 4 and 5 but cannot be conected to vertex 1 or 2 which fails the condition.

vertex 4 and 5 can be connected together to make their degrees as 4 , but we fail at vertex 3.