LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

AK 22

FIFTH SEMESTER – APRIL 2008

MT 5400 – GRAPH THEORY

 

 

 

Date : 05/05/2008                Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

 

SECTION A

Answer ALL the questions.                                                                         (10 x 2 = 20)

 

1. Define a graph.
2. Give an example for the following

(i) Bipartite graph                     (ii) Regular graph

1. Draw a graph with five vertices and find its complement.
2. Define a walk and a path.
3. What is a cut point? Give an example.
4. Give an example of a graph, which is Eulerian but non-Hamiltonian.
5. State Fleury’s algorithm.
6. Define a planar graph and give an example of a non-planar graph.
7. Define the center of the tree.
8. Define the chromatic number of a graph.

 

SECTION B

Answer any FIVE questions.                                                                       (5 x 8 = 40)

 

1. (a) Show that every cubic graph has an even number of vertices.

(b) Prove that .

1. (a) Let G be a k-regular bigraph with bipartition and . Prove that

.

(b) Prove that any self-complementary graph has 4n or 4n+1 vertices.

1. (a) In a graph, prove that any u – v walk contains a u – v path.

(b) Show that a closed walk of odd length contains a cycle.

1. (a) Prove that a graph G with p vertices and  is connected.

(b) If G is not connected then show that  is connected.

1. Prove that a graph G with at least two points is bipartite if and only if all its cycles are of even length.
2. Show that the following statements are equivalent for a connected graph G.

• G is Eulerian.
• Every vertex of G has even degree.
• The set of edges of G can be partitioned into cycles.

1. If G is a graph with p vertices,  and , then prove that G is Hamiltonian.
2. (a) Prove that  is non-planar.

(b) State and prove Euler’s theorem.

 

SECTION C

 

Answer any TWO questions.                                                                       (2 x 20 = 40)

 

1. Prove that the maximum number of edges among all p point graphs with no triangles is , where [x] denotes the greatest integer not exceeding the real number x.

 

1. Let G be a connected graph with at least three vertices. Prove the following:

• G is a block if and only if any two vertices of G lie on a common cycle.
• Any two vertices of G lie on a common cycle if and only if any vertex and any edge of G lie on a common cycle.

 

1. Let G be a (p, q) graph. Show that the following statements are equivalent.

• G is a tree.
• Every two vertices of G are joined by a unique path.
• G is connected and p = q + 1.
• G is acyclic and p = q + 1.

 

1. (a) State and prove five colour theorem.

(b) Prove that the following statements are equivalent for any graph G.

• G is 2-colourable.
• G is bipartite.
• Every cycle of G has even length.

 

Go To Main Page

Latest Govt Job & Exam Updates:

View Full List ...