Question
Verify, “If an undirected graph has exactly two vertices of odd degree there must be a path joining these two vertices.”
(a) Find chromatic number of bipartite graph Km, n.
(b) Is every subgraph of a regular graph regular ? Justify.
(c) Construct a 5-regular graph on 10 vertices.
Show the followings:
a) Show that for a subgraph H of a graph G, ∆(H) ≤ ∆ (G)
b) Show that
Prove the followings:
a) the sum of the degrees of the vertices of G is twice the number of edges
b) If W is a u-v walk joining two distinct vertices u and v, then there is a path joining u and v contained in the walk using the principles of mathematical induction
c) A connected graph G is Eulerian if and only if the degree of each of its vertices is even.
d) If G is a connected planar (p,q)-graph, then the number r of the regions of G is given by r = q - p +2
(a) Solve for by Substitution method.
(b) Solve the recurrence by using iterative approach :
Verify, “If an undirected graph has exactly two vertices of odd degree there must be a path joining these two vertices.”
Define a recurrence relation. Describe the following problems with the help of examples which can be solved through Divide and Conquer technique and Show its recurrence relation.
(i) Binary Search
(ii) Merge Sort
Solve these recurrence relations with a substitution method
To multiply two n-digit numbers, one must do normally
IGNOU Doubts & Queries
Click to Contact Us
Call - 9199852182 Call - 9852900088 myabhasolutions@gmail.com WhatsApp - 9852900088