Name of the Organisation : S.R Group of Institutions (srgi.ac.in)
Type of Announcement : Graph Theory Model Question Paper
Home Page : http://www.srgi.ac.in/
SR Group of Institution, Jhansi
Model Paper -CT-1st (Odd Sem. 2011-12)
Paper Name: Graph theory III Year
Section- A (Objective Type)
Questions from all sections :
Q1. Graph with a finite number of vertices as well as a finite number of edges is called.
a) Planar graph b) Finite graph c) Infinite graph d) None of these
Q2. All vertices are of equal degree is ……………….
a) Null graph b) Regular graph c) Planar graph d) Euler graph
Q3. A graph G= (V, E), it is possible for the edge set E to be empty, such graph is ……..
a) Planar graph b) Euler graph c) Null graph d) None of these
Q4. The number of vertices of odd degree is a graph is always …….
a) Odd b) Even c) May be both d) None of these
Q5. A vertex having no incident edge is ………….
a) end vertex b) isolated vertex c) pendent vertex d) none of these
Q6. A graph G is said to be …… if there is atleast one path between every pair of vertices in G.
a) Disconnected graph b) Connected graph
c) Euler graph d) Hamiltonian graph\
Q7. The maximum degree of any vertex in simple graph
a) n b) n+1 c) n-1 d) 2n
Q8. The size of a simple graph of order n cannot exceed
a) nc1 b) nc2 c) n1 d) none of these
Q9. The maximum number of edges in a simple graph with n vertices
a) n(n-1) b) n(n-1)/2 c) n(n+1) d) none of these
Q10. A graph G with n-vertices is called a tree is
a) G is circuit less and has n-1 edges b) G is minimum connected graph
c) G is connected and is circuit less d) All of the above
Section- B (Short Type)
Answer any seven questions out of the following questions.
Q1. Explain graph with suitable example.
Q2. Explain directed and undirected graph.
Q3. Is it possible to draw a simple graph with 4 vertices and 7 edges? Justify.
Q4. Explain ‘walk and paths’
Q5. Explain Euler graph and Hamiltonian graphs
Q6. Show that the complete graph kn is not a tree when, n>2
Q7. Explain a tree and its kind.
Section- C (Long Type)
Answer any four questions out of the following questions.
Q1. Determine the number of edges in a graph with 6 vertices, 2 of degree 4 and 4 of degree 2. Draw two such graphs.
Q2. Show that the maximum number of edges in a simple graph with n vertices is n(n-1)/2
Q3. Explain types of graphs.
Q4. Explain spanning tree and identify all the spanning tree for given graph.
More question get here : https://www.indianjobtalks.in/uploads/6860-ECS%20505.pdf