BCS405B | GRAPH THEORY

Module 1
Introduction to Graphs: Introduction- Basic definition – Application of graphs – finite, infinite and
bipartite graphs – Incidence and Degree – Isolated vertex, pendant vertex and Null graph. Paths
and circuits – Isomorphism, sub-graphs, walks, paths and circuits, connected graphs, disconnected graphs and components.
Module 2
Eulerian and Hamiltonian graphs: Euler graphs, Operations on graphs, Hamiltonian paths and circuits, Travelling salesman problem. Directed graphs – types of digraphs, Digraphs and binary relation
Module 3
 Trees – properties, pendant vertex, Distance and centres in a tree – Rooted and binary trees, counting trees, spanning trees. Connectivity Graphs: Vertex Connectivity, Edge Connectivity, Cut set and Cut Vertices, Fundamental circuits.
Module 4
Planar Graphs: Planar graphs, Kuratowski’s theorem (proof not required), Different representations of planar graphs, Euler’s theorem, Geometric dual. Graph Representations: Matrix representation of graphs-Adjacency matrix, Incidence Matrix, Circuit Matrix, Path Matrix
Module 5
 Graph Colouring: Colouring- Chromatic number, Chromatic polynomial, Matchings, Coverings, Four colour problem and Five colour problem. Greedy colouring algorithm.

BCS405B | Model Question Paper with Solution

MQP Solution
Access well‑organized Model Question Paper with step‑by‑step, point‑wise solutions. Each solution is created to save your time, clarify concepts, and help you revise effectively. 

BCS405B | Passing Package
( Score More )

Passing Package
A smart package made for VTU students! Selected important questions prepared to cover exactly what matters in VTU exams. Clear, simple, and quick to revise – perfect for last‑minute preparation and aiming for better marks with confidence.