Question 1:
a) Define Euler line and Euler graph with two examples?
b) A connected graph G is an Euler graph if and only if all vertices of G are of even degree.
Question 2: Define the terms multigraph and simple graph. Differentiate between them with the help of example.
Question 3:
a) Prove that Petersen graph is neither Eulerian nor Semi Eulerian.
b) Prove that connected graph is Semi-Eulerian if and only if its has actually 0 or 2 vertices of add degree.
Question 4: Define the term simple graph. Prove that a simple graph with n position and k components can have at most (n-k)(n-k+1)/2 lines?
Question 5:
a) Define chromatic number of a graph and prove that every tree with 2 or more vertices is 2-chromatic?
b) Define covering proving that covering of graph is minimal if graph comprises of no path of length 3 or more?
Question 6:
a) Prove: In any nondirected graph there is an even no of vertices of odd order.
b) Is there a simple graph with degree sequence (1,1,3,3,3,4,6,7)? Give reason?
Question 7:
a) Define simple graph, connected graph, degree of a vertex and minimal cut of a graph.
b) show that the maximum no of edges in a simple graph of n vertices is = n(n-1)/2
Question 8:
a) Describe the terms: Cycle, tree, forest and spanning tree.
b) State and explain Kruskals algorithm