SAMPLE QUESTIONS (GRAPH THEORY)

1. Chapter 1 & 2 : Introduction & paths and Circuits
----------------------------------------------------
   1.1 	Show that the number of vertices of odd degree in a graph is always
	even.

   1.2 	Show that the maximum number is edges in a simple graph with n 
	vertices is n(n-1)/2.

   1.3	Consider the following situation :
		There are four applicants A, B, C and D to fill six vacant 
	positions P, Q, R, S, T and U. Applicant A is qualified to fill P, 
	Q, R, S, or U. Applicant B can fill Q or T. Applicant C can fill B
	or S. Applicant D can fill P and S.

	Represent the above situation by a graph.

   1.4 	Prove that a simple graph with n vertices must be connected if it 
	more than [(n-1)(n-2)]/2 edges.

   1.5 	In a graph G let p1 and p2 be two different paths between two given 
	vertices. Prove that the ring sum of p1 and p2 is a circuit or a set
	of circuits in G.

   1.6 	Definitions :
		Simple graph, Regular graph, Complete graph, Walk, Path,
	Circuit, Hamiltonian Path, Euler graph, separable graph, 
	Isomorphism etc.

2. Chapter 3 : Trees and Fundamental Circuits
---------------------------------------------
   2.1	Show that the minimum possible height of an n-vertex binary tree
	is ceiling of [ log(n+1) - 1 ]. (log is of base 2)

   2.2  Find out a shortest spanning tree of a given weighted graph by 
	Kruskal's method ( or by Prims method)

   2.3 	Give an outline of the Prim's algorithm to find out a shortest 
        spanning tree of a graph.

   2.4  Let T1 and T2 be two spanning trees of a connected graph g. If edge e
	is in T1 but not in T2, prove that there exists another edge in f in
	T2 but not in T1 such that subgraphs ((T1 - e) U f) and ((t2 - f) U e)
	are also spanning trees of G. 

   2.4	Definitions :
		Binary tree, Spanning tree, Fundamental Circuits, Weighted
	Path Length, Rank, Nullity etc.


3. Chapter 4 : Cut-sets and Cut-vertices
----------------------------------------
   3.1 	Definitions :
		Cut-set, Cut-vertices, Connectivity(Edge & vertex),
	Fundamental Cut-sets,  Thickness, Crossing number etc.

   3.2 	Show that a graph is nonseparable if and only if every vertex pair can
	be placed in some circuit in G.

   3.3  What is 2-isomorphism ?

   3.2  When two graphs are said to have circuit correspondance?