Scribd
Upload
71 views3 pages

GT

This document outlines the sections and questions for a Graph Theory exam. Section A contains 10 short answer questions defining graph theory terms like simple graph, path, connectivity, tree, matching, and more. Section B has 5 longer answer questions proving properties about graphs, trees, matchings, and colorings. Section C consists of 3 essay questions, asking to show properties about connectedness in the complement of a disconnected graph, 2-connectivity, Hall's theorem on matchings, Brook's theorem on colorings, and proving K5 is non-planar.

Uploaded by

Sanware Cola
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
71 views3 pages

GT

This document outlines the sections and questions for a Graph Theory exam. Section A contains 10 short answer questions defining graph theory terms like simple graph, path, connectivity, tree, matching, and more. Section B has 5 longer answer questions proving properties about graphs, trees, matchings, and colorings. Section C consists of 3 essay questions, asking to show properties about connectedness in the complement of a disconnected graph, 2-connectivity, Hall's theorem on matchings, Brook's theorem on colorings, and proving K5 is non-planar.

Uploaded by

Sanware Cola
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

S.No.

3152 17PMA14

(For the candidates admitted from 2017–2018 onwards)

M.Sc. DEGREE EXAMINATION, NOVEMBER 2020.

Fourth Semester

Mathematics

GRAPH THEORY

Time : Three hours Maximum : 75 marks

SECTION A — (10 × 2 = 20 marks)


Answer ALL questions.

1. Define simple graph.

2. Define path.

3. Define connectivity.

4. Define tree.

5. Define matching

6. Define independent set.

7. Define vector colouring.

8. State chromatic number.


9. Define exterior face.

10. State Euler’s formula.

SECTION B — (5  5 = 25 marks)

Answer ALL questions.

11. (a) Prove that in any graph the number of


vertices of odd degree is even.
Or
(b) Write short notes on Incidence and Adjacency
matrices with example.

12. (a) If G is a tree then show that e  v  1 .


Or
(b) Show that a connected graph is a tree if and
only if every edge is a cutedge.

13. (a) Let M be a matching and k be a covering such


that M  k , then prove that M is maximum
matching and k is a minimum covering.
Or
(b) If   0 then show that       v .

2 S.No. 3152
14. (a) If G is k-critical then prove that f g   k  1 .
Or
(b) Prove that in a critical graph G. no vertex cut
is a clique.

15. (a) If the girth k of a connected plane graph is at


kn  1
least 3, then prove that m  .
k2
Or
(b) Prove that every planar graph is 6 vertex
colourable.

SECTION C — (3  10 = 30 marks)
Answer any THREE questions.

16. If a simple graph G is not connected, then show


that G C is connected.

17. A graph G with at least 3 vertices is 2-connected if


and only if 2 vertices of C are connected by at least
2 IDP.

18. State and prove Hall’s theorem.

19. State and prove Brook’s theorem.

20. Prove that K 5 is non planar graph.


———————

3 S.No. 3152

You might also like