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.
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?
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?
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?
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
a) Describe the terms: Cycle, tree, forest and spanning tree.
b) State and explain Kruskals algorithm