LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034  B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – NOV 2006

         MT 5400 – GRAPH THEORY

(Also equivalent to MAT 400)

Date & Time : 03-11-2006/9.00-12.00         Dept. No.                                                       Max. : 100 Marks

Part A

Answer all the questions. Each question carries 2 marks.

1. Give an example of a regular graph of degree 0.
2. The only regular graph of degree 1 is K₂. True or false? Justify your answer.
3. What is a self-complementary graph?
4. What is the maximum degree of any vertex in a graph on 20 vertices?
5. Show that the two graphs given below are not isomorphic.

6. Give an example of a closed walk of even length which does not contain a cycle.
7. Draw all non-isomorphic trees on 6 vertices.
8. Give an example of a graph which has a cut vertex but does not have a cut edge.
9. Define a block.
10. Give an example of a bipartite graph which is non-planar.

Part B

Answer any 5 questions. Each question carries 8 marks.

11. (a). Prove that in any graph,

(b). Draw the eleven non-isomorphic sub graphs on 4 vertices.                     (4+4)

12. (a). Define the incidence and adjacency matrices of a graph. Write down the

adjacency matrix of the following graph:

(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)

13. Prove that the maximum number of edges among all graphs with p vertices, where p is odd, with no triangles is [p² / 4], where [x] denotes the greatest integer not exceeding the real number x.
14. (a). Let G be a k-regular bipartite graph with bipartition (X, Y) and k > 0. Prove

that

(b). Show that if G is disconnected then G^C is connected.                (4 + 4)

15. (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)

16. Prove that a graph G with at least two points is bipartite if and only if all its cycles are of even length.

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

(b). Prove that every tree has a centre consisting of either one vertex or two

adjacent vertices.

18. Let G be graph with with p ≥ 3 and, then prove that G is Hamiltonian.

Part C

Answer any 2 questions. Each question carries 20 marks.

19. Let G₁ be a (p₁, q₁)-graph and G₂ a (p₂, q₂)-graph. Show that
20. G₁ x G₂ is a (p₁ p₂, q₁p₂ + q₂p₁)-graph and
21. G₁[G₂ ] is a (p₁ p₂, q₁p₂² + q₂p₁)-graph.

20. Prove that the following statements are equivalent for a connected graph G.
21. G is Eulerian.
22. Every vertex of G has even degree.
23. The set of edges of G can be partitioned into cycles.

21. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
22. G is a tree.
23. Any two vertices of G are joined by a unique path.
24. G is connected and p = q + 1.
25. G is acyclic and p = q + 1.

22. (a). Obtain Euler’s formula relating the number of vertices, edges and faces of

a plane graph.

(b). Prove that every planar graph is 5-colourable.                             (10+10)

Go To Main Page

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc.  DEGREE EXAMINATION –MATHEMATICS

FIFTH SEMESTER – APRIL 2007

MT 5400 – GRAPH THEORY

Date & Time: 03/05/2007 / 9:00 – 12:00        Dept. No.                                                     Max. : 100 Marks

Part A

Answer all the questions. Each question carries 2 marks.

1. Show that K_p – v = K_{p – 1}.
2. Give an example of a self-complementary graph.
3. Write down the incidence and adjacency matrices of the following graph.

4. Give an example of a disconnected graph with three components each of which is

3-regular.

5. Give an example of a non-Eulerian graph which is Hamiltonian.
6. For what values of m and n is K_m,n Eulerian?
7. Draw all non-isomorphic trees on 5 vertices.
8. Give an example of a closed walk of even length which does not contain a cycle.
9. Define a planar graph and give an example of a non-planar graph.
10. Define the chromatic number of a graph.

Part B

Answer any 5 questions. Each question carries 8 marks.

11. (a). Prove that in any graph G, the sum of degrees of the vertices is twice the number

of edges. Deduce that the number of vertices of odd degree in any graph is even.

(b). Draw the eleven non-isomorphic graphs on 4 vertices.                           (4+4)

12. (a). 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.

(b). Define isomorphism of graphs. If two graphs have the same number of

vertices and same number of edges are they isomorphic? Justify your answer.                                                                                                                           (4+4)

13. (a). Define product and composition of two graphs. Illustrate with examples.

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

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

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

15. (a). Show that if G is disconnected then G^C is connected.

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

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

are of even length.

17. Let v be a vertex of a connected graph. Then prove that the following statements are equivalent:
    1. v is a cut-vertex 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.

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

path.

18. Let G be graph with p ≥ 3 and. Then prove that G is Hamiltonian.

Part C

Answer any 2 questions. Each question carries 20 marks.

19. Prove that the maximum number of edges among all graphs with p vertices with no triangles is [p² / 4], where [x] denotes the greatest integer not exceeding the real number x.                                     (20)
20. (a).Prove that every connected graph has a spanning tree.

(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)
4. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
5. G is a tree.
6. Any two vertices of G are joined by a unique path.
7. G is connected and p = q + 1.
8. G is acyclic and p = q + 1. (20)

22. (a).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.

(b). State and prove the five-colour theorem.                                                 (10+10)

Go To Main Page

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

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

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

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 G – v and G – e.
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 K_n.
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)

11. (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)

12. Let G₁ be a (p₁, q₁)-graph and G₂ a (p₂, q₂)-graph. Show that G₁ + G₂ is a (p₁ + p₂, q₁ + q₂ + p₁p₂) – graph and G₁ x G₂ is a (p₁ p₂, q₁p₂ + q₂p₁) – graph.

13. (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)

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

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

(4+4)

15. (a). Show that if G is disconnected then G^C is connected.

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

(4+4)

16. 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.

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

path.

17. 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.

18. State and prove the five-colour theorem.

PART – C

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

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

triangles is [p² / 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)

20. (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)

21. (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)

22. Let G be a (p, q)-graph. Prove that the following statements are equivalent.
23. G is a tree.
24. Any two vertices of G are joined by a unique path.
25. G is connected and p = q + 1.
26. G is acyclic and p = q + 1.

(20)

Go To Main Page

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

   B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – November 2008

MT 5408 – GRAPH THEORY

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

Time : 9:00 – 12:00

PART – A

ANSWER ALL QUESTIONS                                                                          (10 x 2 = 20)

1. Define a cubic graph.
2. Prove that .
3. Give an example for an isomorphism between two graphs.
4. Define a self complementary graph and give an example.
5. Define walk and and path.
6. Define an eulerian graph.
7. Prove that every Hamiltonian graph is 2-connected.
8. Define the centre of a tree.
9. If G is k-critical, then prove that .
10. Write the chromatic number for .

PART – B

ANSWER ANY FIVE QUESTIONS                                                                 (5 x 8= 40)

11. a) Prove that in any graph G , the number of points of odd degree is even.
12. b) Prove that any self complementary graph has 4n or 4n + 1    (4 + 4)

12. a) Let G be a k regular bigraph with bipartition (V₁,V₂) and k>0. Prove that

.

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

13. Let x be a line of a connected graph G. Then prove that the following are

equivalent

1. x is a bridge of G.
2. ii) There exists a partition of V into subsets U and W such that for each

uU and  wW, the line x is on every  u – w  path.

iii) There exist two points u , w  such that the line x is on every  u –  w path.

14. Prove that a line x of a connected graph G is a bridge if and only if x is not

on any cycle of G.

• a) Prove that every tree has a centre consisting of either one point or two

adjacent  points.

1. b) Prove that a graph G with p points and is connected.               (4 + 4)

• Prove that every nontrivial connected graph has atleast two points which are not cutpoints.
• If G is a graph with vertices and , then show that G is Hamiltonian.
• State and prove five colour theorem.

PART – C

ANSWER ANY TWO QUESTIONS                                                               (2 x 20 = 40)

• a) Prove the maximum number of lines among all p point graphs with no

triangles is .

1. b) Let G₁ be a  graph and G₂ a    Then prove that is

a  graph.                                                                   (15 + 5)

• a) Prove that a graph G with at least two points is bipartite if and only if its cycles

are of even length.

1. b) State and prove Chavatal theorem. (10 + 10)

• Prove that the following are equivalent for a connected graph G.

1. G is eulerian.
2. Every point of G has even degree.

• The set of edges of G can be partitioned into cycles.

• Let G be a tree. Then prove that following are equivalent.

1. i) G is a tree.
2. ii) Every two points of G are joined by a unique path.

iii)   G is connected and  p = q + 1.

1. iv) G is acyclic and  p = q +

Go To Main Page

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

B.Sc. DEGREE EXAMINATION – MATHEMATICS

FIFTH SEMESTER – APRIL 2012

MT 5408 – GRAPH THEORY

Date : 27-04-2012              Dept. No.                                        Max. : 100 Marks

Time : 1:00 – 4:00

PART A

Answer ALL the questions                                                                                          (10 x 2 =20)

1. Define a complete bipartite graph.
2. Prove that every cubic graph has an even number of points.
3. If G₁ = K₂ and G₂ = C₃ then find

• G₁G₂ (ii) G₁ + G₂

4. Define distance between any two points of a graph.
5. Define an Eulerian graph and give an example.
6. Prove that every Hamiltonian graph is 2-connected.
7. Draw all possible trees with 6 vertices.
8. Define an eccentricity of a vertex v in a connected graph G.
9. Is K_3,3 planar? If not justify your answer.
10. Find the chromatic number for the following graph.

PART B

Answer any FIVE questions                                                                                                    (5 x 8 =40)

11. (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) Prove that                                                                                      (5+3)

12. If Let be a graph and  be a  graph then prove that

(i)  is a  graph.

(ii)  is a  graph.

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

(b) If a graph G is not connected then prove that the graph  is connected.                   (5+3)

14. (a) Prove that a line x of a connected graph G is a bridge if and only if x is not on any cycle of G.

(b) Prove that every non – trivial connected graphs has atleast two points which are not cut points.                                                                                                                              (5+3)

15. If G is a graph with vertices and , then prove that G is Hamiltonian.
16. (a) Prove that every tree has a centre consisting of either one point or two adjacent points.

(b) Let T be a spanning tree of a connected graph. Let x = uv be an edge of G not in T. Then   prove that T + x contains a cycle.                                                                                  (4+4)

17. State and prove Euler’s theorem.
18. Prove that every planar graph is 5-colourable.

PART C

Answer any TWO questions                                                                                    (2 x 20 =40)

19. (a) Prove that the maximum number of lines among all p point graphs with no triangles is .

(b) Let  be a  graph then prove that .                                              (15 +5)

20. (a) Prove that a graph G with atleast two points is bipartite if and only if all its cycles are of even length.

(b) Let G be a connected graph with atleast three points then prove that G is a block if and only if any two points of G lie on a common cycle.                                                    (12+8)

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

(i) G is eulerian.

(ii) Every point of G has even degree.

(iii) The set of edges of G can be partitioned into cycles.

(b) Show that the Petersen graph is nonhamiltonian.                                                       (12+8)

22. (a) Let be a graph then prove that the following statements are equivalent

(i) G is a tree.

(ii) Every two points of G are joined by a unique path.

(iii) G is connected and .

(iv) G is acyclic and .

(b) Prove that every uniquely n – colourable graph is (n – 1) connected.             (14+6)

Go To Main Page