DSTL Unit 5 Notes AKTU (BCS303)

AKTU · BTECH · Semester 3 · Discrete Structures & Theory of Logic · Unit 5 · Notes

AKTU Discrete Structures & Theory of Logic (BCS303) Unit 5 notes for B.Tech Semester 3 – Graphs & Combinatorics. Topics: Graphs & Terminology, Isomorphism &…

Open the interactive reader to study this resource on AcademicArk.

Unit 5: Graphs & Combinatorics – AKTU syllabus topics

  • Graphs & Terminology
  • Isomorphism & Homeomorphism
  • Euler & Hamiltonian Paths
  • Graph Coloring
  • Combinatorics & Counting

Most asked AKTU PYQ questions from Unit 5

  1. Q2e. If a connected planar graph G has n vertices, e edges and r region, then n – e + r = 2. (10 marks, 2020-21)
  2. Q2e. Define planar graph. Prove that for any connected planar graph, v - e + r = 2 Where v, e, r is the number of vertices, edges, and regions of the graph respectively. (10 marks, 2019-20)
  3. Q1i. Explain Euler’s formula. Determine number of regions if a planar graph has 30 vertices of degree 3 each. (2 marks, 2021-22)
  4. Q7b. Show that K3,3 satisfies in equality |E| ≤ 3 |V| – 6, but it is non planar.(V=No. of Vertices, E=No. of Edges, R=No. of Regions) (7 marks, 2023-24)
  5. Q1h. Describe Planar graph and express Euler’s formula for planar graph. (2 marks, 2022-23)
  6. Q7b. i. Justify that “In a undirected graph the total number of odd degree vertices is even”. ii. Justify that “The maximum number of edges in a simple graph is n(n-1)/2”. (10 marks, 2021-22)
  7. Qa. Let G be a 3-regualr graph with n vertices. What is the sum of the degree of the vertices? Show that in such a graph n must be even. (7 marks, 2025-26)
  8. Q2e. Explain Pigeon hole principle. Describe generalized form of Pigeon hole principle. If 6 colors are to paint 37 homes. Show that at least 7 of them will be of same color. (7 marks, 2023-24)
  9. Q1j. Explain pigeonhole principle with example. (2 marks, 2021-22)
  10. Q1h. Show that there does not exist a graph with 5 vertices with degrees 1, 3, 4, 2, 3 respectively. (2 marks, 2019-20)

AKTU paper codes: BCS303, KCS303, BCS303H, KCS303H

Other Discrete Structures & Theory of Logic units

Discrete Structures & Theory of Logic previous year papers

More Discrete Structures & Theory of Logic resources

More versions of this resource

Browse all notes · Semester 3 notes