Lovely Professional University 2008 B.Tech Information Technology Assignment 1- Discrete mathematics - Question Paper

Assignment 1


Q1 Consider the graph in fig one and obtain (a) the degree of every vertex and verify the handshaking lemma
(b) all simple paths from A to G
(c) all trails (Distinct edges) from B to C
(d) d(A,C), The distance from A to C
(e)Diameter (G)

(see image in attachment)

Q2 Consider the graph as shown in the fig one and obtain all the cycles, all cut points and bridges if any.

Q3 Consider the subsequent graph. obtain the sub graph H(V’,E’) generated by:
(a) V’={B,C,D,E,F};(B) V’={A.C,E,G,H};(C) V’={B,D,E,H};(D) V’={C,F,G,H}
(b) Which of them are isomorphic and which are homomorphic?

(see image in attachment )

Q4 Can a simple graph exists with 15 vertices every of degree five?

Q5Consider the multigraph G as shown in the figure (a)Which of them are connected? if they are not obtain the number of connected components .(b)which are cycle free .if they are not obtain the number of cycles (c)Which are loop free and Which are simple graphs?

(see diagram in attachment)

Q6 Show that graph g with n vertices must have n-1 edges ?

Q7Draw 2 3-regular graphs with eight vertices ?

Q8 consider every graph in G .Find the euler path or euler circuit if exists?and if does not why?
(see image in attachment )

Q9 Consider every graph in G. obtain the Hamiltonian Path or circuit if exists and if does not why???

Q10 Consider the complete graph Kn
(a) Find the no of m edges in Kn
(b) Find the degree of every vertex in Kn
(c) Find those values of n for which Kn is regular

Q11 Suppose that G and G* ARE HOMOMORPHIC. Show that G is Eulerian if and only if G* is Eulerian.

Earning:   Approval pending.