Question

(4)1. Draw a directed graph represented by the given adjacency matrix 0 1 0 1] 1 01 0 (4)2. If possible, draw a graph with vertices having degrees: 4,3,3,3,2,1.

Answer 1

(4) 1 . Show a directed graph of given adjacency matrix

J23 2 3 1 o 2

--------------------------------------------------------------------------------------------------------------------------------------------------------

(4) 2 . If possible draw a graph with vertices having degrees:4,3,3,3,2,1

• A sequence d₁,d₂ ,.......,d_nof non negative integers of a graph G , if the vertices of a the graph labeled v₁,v₂,....v_n such that deg(v_i)=d_i for all i=1,2,3,......,n.
• So here, graph sequence 4,3,3,3,2,1.
• So the graph needs to be 6 vertices with sequence degree.
• Necessary conditions to create a graph are:

                    * vertices and sequence number are equal and also even.[Here it's 6.which satisfy the condition]

                    *sum of the sequence is also even [Here it's 16,satisfy the condition]

                   *Sequence always less than or equal to n-1 [here n=6,n-1=5 all members less than 6]

• Next we have to check compulsory condition. That is called Haval & Hakimi theorem
• Theorem:There is a graph with degree sequence (d₁,d₂,...,d_n-1,d_n) where d_i?d_i+1if and only if there is a graph with degree sequence (d₂?1,d₃?1,...,d_d1+1?1,d_d1+2,...,d_n).

Hene chuck Seapunce H, 3, 3, 3, Remove st element 3, 3, 3, 2 2, 2 2, opl all 1 values ㅘ사 Hena Cue

2, 3