I slightly understand the concepts however I just need a wal

I slightly understand the concepts however I just need a walkthrough to get my head around things :)

(a) Consider the sequence of integers (1, 1, 1, 1, 3, 3, k) with k >=?? 3.

(i) Show that if k = 4 then sequence is graphic. Draw a graph corre- sponding to this sequence.

(ii) Show that if k ?= 4 then the sequence is not graphic.

Solution

Using handshake theorem, the sum of the degrees of the graph must be even in order to be a graphic sequence

Hence, (1+1+1+1+3+3+k) must be even

10 + k must be even

Since 10 is even, hence k must be even in order to satisfy the handshake theorem

Hence it will be only valid for k being an even integer

a) Let us say that the sequence has value of K=4, then the graph possible will look like below

the possible graph can be found on below link(sorry chegg upload feature is not working)

http://postimg.org/image/otd60kgtt/

b) The next even integer will be 6 which implies that the graph is connected to all the vertices hence it cannot be possible to then accomodate other degrees of the graph and k=8, it is not possible since there are only 7 vertices in the graph

Hence the given sequence will not be a graphic sequence with K>=4