Scribd
Upload
53 views2 pages

Graph Theory PYQs with Solutions

The document contains previous year questions (PYQs) on graph theory, including spanning trees, depth-first search (DFS), breadth-first search (BFS), Euler circuits, planarity, chromatic numbers, Hamiltonian cycles, and isomorphism. It provides step-by-step solutions for each question, detailing the processes and outcomes. Key findings include the existence of an Euler trail, the requirement of three colors for an odd cycle, and the isomorphism of a graph to K5.

Uploaded by

ganeshvutukuri93
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
53 views2 pages

Graph Theory PYQs with Solutions

The document contains previous year questions (PYQs) on graph theory, including spanning trees, depth-first search (DFS), breadth-first search (BFS), Euler circuits, planarity, chromatic numbers, Hamiltonian cycles, and isomorphism. It provides step-by-step solutions for each question, detailing the processes and outcomes. Key findings include the existence of an Euler trail, the requirement of three colors for an odd cycle, and the isomorphism of a graph to K5.

Uploaded by

ganeshvutukuri93
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

UNIT–5 : GRAPH THEORY – PYQs WITH FULL STEP-BY-STEP SOLUTIONS

============================================================

PYQ 1 — SPANNING TREE + DFS + BFS

---------------------------------

Graph G: V={A,B,C,D,E}, E={AB, AC, BD, CE, DE}

(a) Spanning Tree

Step 1: Need 4 edges (5–1).

Step 2: Select edges avoiding cycles: AB, AC, BD, DE.

Step 3: All vertices included, no cycle → valid.

(b) DFS (A → alphabetical)

Steps:

A→B→D→E→C

Final DFS order: A, B, D, E, C.

(c) BFS (A → alphabetical)

Queue Steps:

A | enqueue B,C

Visit B | enqueue D

Visit C | enqueue E

Order = A, B, C, D, E.

------------------------------------------------------------

PYQ 2 — EULER CIRCUITS + PLANARITY

-----------------------------------

Given degrees: {3,3,2,2,2,2}

(a) Euler Path/Circuit:

Step 1: Count odd-degree vertices = 2.

Step 2: If 2 odd → Euler Trail exists, no circuit.

Final: Euler trail exists, circuit does not.

(b) Euler Formula:


V=6, E=7

F = 2 - 6 + 7 = 3.

Check Planarity:

E ≤ 3V - 6 → 7 ≤ 12 ✓

Graph may be planar.

------------------------------------------------------------

PYQ 3 — CHROMATIC NUMBER + HAMILTONIAN + ISOMORPHISM

-----------------------------------------------------

Graph: C5 (cycle of 5 vertices)

(a) Chromatic Number:

Step 1: Odd cycle ⇒ cannot 2-color.

Step 2: 3 colors required.

Answer: χ(C5)=3.

(b) Hamiltonian:

Cycle C5 itself is Hamiltonian:

v1→v2→v3→v4→v5→v1.

(c) Isomorphism:

Graph H with 5 vertices, each deg=4.

Means each vertex connected to all others → K5.

Thus H ≅ K5.

------------------------------------------------------------

END OF PDF CONTENT

You might also like