Loyola College B.Sc. Mathematics Nov 2008 Graph Theory Question Paper PDF Download

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

AB 22

FIFTH SEMESTER – November 2008

MT 5400 – GRAPH THEORY

Date : 12-11-08                     Dept. No.                                        Max. : 100 Marks

Time : 9:00 – 12:00

PART- A

Answer ALL the questions. Each question carries 2 marks.                                (10 x 2 = 20 marks)

1. Show that every cubic graph has an even number of vertices.
2. Let G = (V, E) be a (p, q) graph. Let and . Find the number of vertices and edges in Gv and Ge.
3. Define a walk and a path.
4. What is a connected graph?
5. Give an example of a disconnected graph with 4 components.
6. Draw all non-isomorphic trees on 6 vertices.
7. Define an Eulerian trail and a Hamiltonian cycle.
8. What is a cut edge? Give an example.
9. Determine the chromatic number of Kn.
10. Define a planar graph and give an example of a non-planar graph.

PART –  B

Answer any FIVE questions. Each question carries EIGHT marks.                   (5 x 8 = 40 marks)

1. (a). Show that in any group of two or more people there are always two with exactly

the same number of friends inside the group.

(b). Let G be a (p, q)-graph all of whose vertices have degree k or k + 1. If G has t

vertices of degree k then show that t = p(k+1)-2q.                                                           (4+4)

1. Let G1 be a (p1, q1)-graph and G2 a (p2, q2)-graph. Show that G1 + G2 is a (p1 + p2, q1 + q2 + p1p2) – graph and G1 x G2 is a (p1 p2, q1p2 + q2p1) – graph.

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

(b).Prove that a graph with p vertices and  is connected.                                       (4+4)

1. (a). Prove that a closed walk of odd length contains a cycle.

(b). Find the composition of the following graphs.

(4+4)

1. (a). Show that if G is disconnected then GC is connected.

(b). Determine the centre of the following graph.

(4+4)

1. Let v be a vertex of a connected graph. Then prove that the following statements are equivalent:
1. v is a cut-point of G.
2. There exists a partition of V – {v} into subsets U and W such that for each

uU and  wW, the point v is on every (u, w) – path.

1. There exist two points u and w distinct from v such that v is on every (u, w)-

path.

1. Let G be a connected plane graph with V, E and F as the sets of vertices, edges and faces respectively. Then prove that | V | – | E | + | F | = 2.

1. State and prove the five-colour theorem.

PART – C

Answer any TWO questions. Each question carries 20 marks.                            (2 x 20 = 40 marks)

1. (a). Prove that the maximum number of edges among all graphs with p vertices with no

triangles is [p2 / 4], where [x] denotes the greatest integer not exceeding the real number x.

(b). Show that an edge e of a graph G is a cut edge if and only if it is not contained in any cycle

of G.                                                                                                                                (15+5)

1. (a). Prove that a graph G with at least two points is bipartite if and only if all its cycles

are of even length.

(b). Let G be graph with with p ≥ 3 and. Then prove that G is Hamiltonian.                      (10+10)

1. (a). If G is Hamiltonian, prove that for every non-empty proper subset S of V, the

number of components of G \ S , namely, ω(G \ S) ≤ | S |.

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

1. G is Eulerian.
2. Every vertex of G has even degree.
3. The set of edges of G can be partitioned into cycles.                        (5+15)

1. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
2. G is a tree.
3. Any two vertices of G are joined by a unique path.
4. G is connected and p = q + 1.
5. G is acyclic and p = q + 1.

(20)

Go To Main Page

Latest Govt Job & Exam Updates:

View Full List ...

© Copyright Entrance India - Engineering and Medical Entrance Exams in India | Website Maintained by Firewall Firm - IT Monteur