Loyola College P.G. 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

Loyola College M.Sc. Mathematics April 2003 Graph Theory Question Paper PDF Download

 

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034.

M.Sc. DEGREE EXAMINATION – Mathematics

FourTH SEMESTER – APRIL 2003

MT 4951 / M 1056  –  GRAPH THEORY

 

23.04.2003

1.00 – 4.00                                                                                                     Max : 100 Marks

      Answer ALL questions. Each question carries 25 marks.

 

  1. (a) Obtain a necessary and sufficient condition for a sequence (d1, d2, …,dn) to be graphic.

(OR)

(b) Prove that a graph is bipartite if and only if it contains no odd cycle.          (8 marks)

(c) (i) Prove, with usual  notation, that  .

(ii) Find the shortest distance from the vertex uo  to all other vertices in the following
graph.

 

 

 

 

 

 

(OR)

(d) (i) Prove that a vertex  v of a tree G is a cut vertex of G if and only if d (v)>1.   Deduce
that every nontrivial loopless connected graph has at least two vertices that are not cut
vertices.

(ii)State Cayley’s formula and find the number of distinct spanning trees of the following
graph.                                                                                                (8+9 marks)

 

 

 

  1. (a) Define connectivity and edge-connectivity of a graph.   Prove, with usual notation, that
    .

(OR)

  • If G is 2-connected, then prove that any two vertices of G lie on a common cycle.

(8 marks)

  • (i) Prove that a non empty connected graph is Eulerian if and only if it has no vertex of
    odd degree.

(ii) Obtain Chvatal’s sufficient condition for a simple graph to be Hamiltonian.

(OR)

  • (i) Let G be a simple graph and let u and v be non-adjacent vertices in G such that
  1. n. Prove that G is Hamiltonian  is Hamiltonian.

(ii) Describe Chinese postman problem. State Fleury’s algorithm. Find an optimal

four in the following graph.

 

 

 

 

 

 

 

 

 

 

 

 

  1. (a) Prove that a matching M in G is a maximum matching if and only if G contains no
    M-augmenting path.

(OR)

(b)  Prove , with usual notation, that n if                                      (8 marks)

  • (i) State and prove Hall’s theorem.

(ii)  Find an optimal matching in the graph given by the following matrix.

 

(OR)

  • (i) Define an independent set. Prove with usual notation that n.

(ii) Prove that in a bipartite graph the number of edges in a maximum matching is the
same as the number of vertices in a minimum covering.                          (8+9 marks)

  1. (a) State and prove Brook’s theorem.

(OR)

(b)  Let G be a k-critical graph with a 2-vertex cut {u, v}. Prove that  .

(8 marks)

(c)  State and prove kuratowski’s theorem.

(OR)

  • (i) Obtain Euler’s formula and deduce that k5 is non-

(ii)  State and prove the five-colour theorem.                                                (9+8 marks)

 

 

 

Go To Main page

Loyola College M.Sc. Mathematics April 2012 Graph Theory Question Paper PDF Download

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

M.Sc. DEGREE EXAMINATION – MATHEMATICS

FOURTH SEMESTER – APRIL 2012

MT 4802 – GRAPH THEORY

 

 

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

Time : 1:00 – 4:00

 

 

Answer all the questions. Each question carries 25 marks.

 

  1. (a) State Cayley’s formula and determine the number of spanning trees of the following graph.

 

(8)

(OR)

(b) Define a graphic sequence. Obtain a necessary and sufficient condition for a sequence d = (d1, d2dn) to be graphic.                                                                         (8)

 

(c) (i) Obtain a characterization for bipartite graphs.

(ii) Prove that an edge of a graph G is a cut edge if and only if it is contained in no cycle of G.                                                                                                 (8 + 9)

(OR)

(d) Determine the shortest path / distance between u0 and all other vertices of the following graph.

(17)

 

  1. (a) Prove with usual notation that . (8)

(OR)

(b) Prove that a simple graph with  is Hamiltonian if and only if its closure is Hamiltonian.                                                                                               (8)

 

(c) (i) If G is a non-Hamiltonian simple graph with n ≥ 3, then prove that G is degree-majorised by some Cm, n .

(ii) Prove that a nonempty connected graph is Eulerian if and only if it has no vertex of odd degree.                                                                                        (7 + 10)

(OR)

(d) Describe the Chinese Postman problem. Obtain an optimal tour in the following weighted graph.

(17)

 

  1. (a) State and prove Berge theorem on maximum matching. (8)

(OR)

(b) State Kuhn-Munkres algorithm.                                                                            (8)

 

(c) (i) State and prove Hall’s theorem.

(ii) Prove that in a bipartite graph, the number of edges in a maximum matching is equal to the number of vertices in a minimum covering.                                 (9 + 8)

(OR)

(d) Prove, with usual notation, that a + b = n = a ¢ + b ¢, if d > 0.                           (17)

 

  1. (a) Let G be a k-critical graph with a 2-vertex cut {u, v}. Then prove that G = G1 G2 where Gi is a {u, v} – component of type i ( i = 1, 2) and that G1 + uv is k – critical.                                                                                                                                   (8)

(OR)

(b) Obtain Euler’s formula and deduce that K5 are non-planar.                                 (8)

 

(c) Prove that a graph is planar if and only if it contains no subdivision of K5 or K3, 3.

(17)

(OR)

(d) (i) State and prove Brook’s theorem.

(ii) State and prove five color theorem.                                                                (8 + 9)

 

Go To Main page

 

 

 

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

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

AA 08

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

 

 

 

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

 

Part B

Answer any 5 questions. Each question carries 8 marks.

 

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

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

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

  1. Prove that the maximum number of edges among all graphs with p vertices, where p is odd, with no triangles is [p2 / 4], where [x] denotes the greatest integer not exceeding the real number x.
  2. (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 GC is connected.                (4 + 4)

 

  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. Prove that a graph G with at least two points is bipartite if and only if all its cycles are of even length.

 

  1. (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.

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

 

  1. Let G1 be a (p1, q1)-graph and G2 a (p2, q2)-graph. Show that
  2. G1 x G2 is a (p1 p2, q1p2 + q2p1)-graph and
  3. G1[G2 ] is a (p1 p2, q1p22 + q2p1)-graph.

 

  1. Prove that the following statements are equivalent for a connected graph G.
  2. G is Eulerian.
  3. Every vertex of G has even degree.
  4. The set of edges of G can be partitioned into cycles.

 

  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.

 

  1. (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 B.Sc. Mathematics April 2007 Graph Theory Question Paper PDF Download

LOYOLA COLLEGE (AUTONOMOUS), CHENNAI – 600 034

CV 17

B.Sc.  DEGREE EXAMINATION –MATHEMATICS

FIFTH SEMESTER – APRIL 2007

MT 5400GRAPH 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 Kpv = Kp – 1.
  2. Give an example of a self-complementary graph.
  3. Write down the incidence and adjacency matrices of the following graph.

 

 

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

3-regular.

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

 

Part B

 

Answer any 5 questions. Each question carries 8 marks.

 

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

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

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

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

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

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

 

 

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

are of even length.

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

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

path.

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

 

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

 

  1. (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 B.Sc. Mathematics April 2008 Graph Theory Question Paper PDF Download

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

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

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 17

 

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)

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

 

  1. a) Let G be a k regular bigraph with bipartition (V1,V2) and k>0. Prove that

.

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

 

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

 

  1. 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 G1 be a  graph and G2 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 B.Sc. Mathematics April 2012 Graph Theory Question Paper PDF Download

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 G1 = K2 and G2 = C3 then find
  • G1G2 (ii) G1 + G2
  1. Define distance between any two points of a graph.
  2. Define an Eulerian graph and give an example.
  3. Prove that every Hamiltonian graph is 2-connected.
  4. Draw all possible trees with 6 vertices.
  5. Define an eccentricity of a vertex v in a connected graph G.
  6. Is K3,3 planar? If not justify your answer.
  7. Find the chromatic number for the following graph.

 

PART B

Answer any FIVE questions                                                                                                    (5 x 8 =40)

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

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

(i)  is a  graph.

(ii)  is a  graph.

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

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

  1. If G is a graph with vertices and , then prove that G is Hamiltonian.
  2. (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)

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

 

PART C

Answer any TWO questions                                                                                    (2 x 20 =40)

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

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

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

  1. (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

 

 

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