BSc Mathematics SEM V 2016 17 2016-17 Graph Theory & Combinatorics Question Paper - Mumbai University | munotes

Questions asked in this paper

1. Q1 All questi Duration: NB. questions are compu)
2. Q9 Figures to the righ [Total Marks:
   • (1) j is prove that
   • (2) of u; — vy path of length oy gtrace of is the numb ian
   • ii. Show that a nontrivial gra of triangles in G
   • (b) Attempt any TWO question no odd
   • i. Define cut edge of a gra G and only if e i Prove that if is acyclic and hence at an edge e G is a cut edge of 12
   • ii. If 6(G) is minimum de prove that every in a tree is a cut ed gree of G with 6 Os a cut eage e bound (n — 1)/2 sharp? I (G) then show that G is connected Show that a connected (p th — 1)/2 be replaced Show that every nontrivial containg @ cycle if and only if q 2 P vertices. ‘at least two vertices which are non cut
   • (a) Attempt any ONE question:
   • i. Let G be (p,q) gra
3. Q1 G is tree. Show following statements are equivalent
4. Q3 G is connected and lL For any simple graph G vertex where denote 4 degree A edge connectivity and 6(G) denotes the Attempt any TWO qiestions: (12) i Show that spanning tree with n vertices to a vector 4 ii. Let 7(G) qe ote the number of spanning trees of agraph G. Ife E(G) is not a loop, a iii. a tree with at least two vertices contains at least two pendant vertices
   • iv. that there exist a connected graph with degree sequence dy > dy 2 dn if only if 1) 2 1, for ut-edge in G, then board is not

Read from the scan above, so a character or two may differ. The scan is the original.