Skip to content
CampusPrep
CS-302 · Discrete Structure/Quick Revision Short Notes

Discrete Structure (CS-302) - Unit 4 Short Notes

How unit 4 is examined

Handshaking lemma, Euler's formula for planar graphs, isomorphism, Dijkstra, Euler graphs and colouring carry most marks; Hamiltonian, multigraph, connectivity and homomorphism are single 7-markers.

Introduction and basic terminology of graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A graph $G=(V,E)$ has a non-empty set $V$ of vertices and a set $E$ of edges, each joining a pair of vertices.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-01" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="G with deg A=2, B=2, C=3, D=1"><style>#dsfig-u4-01 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-01 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-01 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-01 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-01 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-01 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-01 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-01 .t{fill:#16181D;font-weight:500}#dsfig-u4-01 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-01 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-01 .dot{fill:#16181D}#dsfig-u4-01 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-01 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-01 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-01 .ah{fill:#454C5A}#dsfig-u4-01 .ah.hi{fill:#2340B8}#dsfig-u4-01 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-01 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-01 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-01 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-01 .e{stroke:#B1B7C3}html.dark #dsfig-u4-01 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-01 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-01 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-01 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-01 .t{fill:#E6E8ED}html.dark #dsfig-u4-01 .t.inv{fill:#0F1115}html.dark #dsfig-u4-01 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-01 .dot{fill:#E6E8ED}html.dark #dsfig-u4-01 .ann{fill:#8FA3FF}html.dark #dsfig-u4-01 .lbl{fill:#858D9C}html.dark #dsfig-u4-01 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-01 .ah{fill:#B1B7C3}html.dark #dsfig-u4-01 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-01 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-01 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-01 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh5" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L195,48.5"/><path class="e" d="M57,134.5 L195,203.5"/><path class="e" d="M212,59 L212,193"/><path class="e" d="M229,203.5 L367,134.5"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">G with deg A=2, B=2, C=3, D=1</figcaption></figure>

Key points.

  1. A vertex is a node and an edge is a line joining two vertices, its endpoints, on which it is incident.
  2. Two vertices joined by an edge are adjacent.
  3. The degree $\deg(v)$ is the number of edges at $v$, and a loop adds 2.
  4. In a directed graph the in-degree counts edges entering a vertex and the out-degree counts edges leaving it.
  5. An isolated vertex has degree 0, a pendant vertex has degree 1, and a simple graph has no loops or parallel edges.
  6. A regular graph has equal degrees, and $K_n$ has $\frac{n(n-1)}2$ edges.

Formula. Handshaking lemma: $\sum_{v}\deg(v)=2|E|$. Proof. Each edge has two ends and adds 1 to the degree of each endpoint (a loop adds 2 to one vertex), so summing degrees counts every edge twice.

Odd vertices. Split the sum into even-degree and odd-degree vertices. The total $2|E|$ and the even part are even, so the odd part is even; a sum of odd numbers is even only for an even count, so the number of odd-degree vertices is even.

Example. Degrees 1, 3, 4, 2, 3 sum to $13$, which is odd, so no such graph exists.

Regular binary tree. With $i$ internal nodes (root degree 2, others 3) and $l$ leaves, the degree sum is $3(i-1)+2+l$. It also equals $2(n-1)=2i+2l-2$, so $l=i+1$ and $n=2i+1$, which is odd.

<mark>The sum of the degrees of all vertices equals twice the number of edges, because each edge contributes 1 to the degree of each of its two ends.</mark>

Answer frame. Open with $G=(V,E)$; draw the graph with degrees marked; define vertex, edge, adjacency, incidence, degree; state the lemma with its proof; close with the odd-vertices corollary.

Pitfall: Forgetting that a loop adds 2 to the degree.

Asked: [7 marks] (Dec 2024) Show that there does not exist a graph with 5 vertices with degrees 1, 3, 4, 2, 3 respectively. Asked: [7 marks] (Nov 2019) Prove that the number of vertices of odd degree in a graph is always even. Asked: [7 marks] (Nov 2019) Show that a regular binary tree has an odd number of vertices. Asked: [7 marks] (Nov 2022) Prove that the sum of the degrees of all vertices in a graph G is twice the number of edges. Asked: [7 marks] (Jun 2025) Define graph theory and explain the basic terminology of graphs such as vertices, edges, degree and adjacency.

Planar graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. A graph is planar if it can be drawn in the plane with no two edges crossing except at vertices; the drawing divides the plane into regions, one of them unbounded.

Key points.

  1. Euler's formula: a connected planar graph with $v$ vertices, $e$ edges and $r$ regions satisfies $v-e+r=2$.
  2. Every edge borders at most two regions, so the region degrees add up to $2e$.
  3. In a simple connected planar graph each region has at least 3 edges, so $3r\le2e$ and $e\le3v-6$.
  4. $K_5$ and $K_{3,3}$ are non-planar, and by Kuratowski's theorem a graph is planar iff it contains no subdivision of either.
  5. A simple graph on $n$ vertices has at most $\binom n2=\frac{n(n-1)}2$ edges, because there is one possible edge per pair of vertices.

Proof of Euler's formula (induction on $e$). Base: a tree has $e=v-1$ and $r=1$, so $v-(v-1)+1=2$. Step: if the graph has a cycle, delete one cycle edge; two regions merge, so $r$ and $e$ each fall by 1 and $v-e+r$ is unchanged. By hypothesis the smaller graph gives 2, so the original does too.

Example (5 vertices, 5 regions). $e=v+r-2=8$. A square $ABCD$ with a centre $O$ joined to all corners has $v=5$, $e=8$, four triangles plus the outer region so $r=5$, and $5-8+5=2$. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-02" viewBox="0 0 424 338" width="424" height="338" role="img" aria-label="5 vertices, 8 edges, 5 regions"><style>#dsfig-u4-02 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-02 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-02 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-02 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-02 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-02 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-02 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-02 .t{fill:#16181D;font-weight:500}#dsfig-u4-02 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-02 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-02 .dot{fill:#16181D}#dsfig-u4-02 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-02 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-02 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-02 .ah{fill:#454C5A}#dsfig-u4-02 .ah.hi{fill:#2340B8}#dsfig-u4-02 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-02 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-02 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-02 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-02 .e{stroke:#B1B7C3}html.dark #dsfig-u4-02 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-02 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-02 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-02 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-02 .t{fill:#E6E8ED}html.dark #dsfig-u4-02 .t.inv{fill:#0F1115}html.dark #dsfig-u4-02 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-02 .dot{fill:#E6E8ED}html.dark #dsfig-u4-02 .ann{fill:#8FA3FF}html.dark #dsfig-u4-02 .lbl{fill:#858D9C}html.dark #dsfig-u4-02 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-02 .ah{fill:#B1B7C3}html.dark #dsfig-u4-02 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-02 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-02 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-02 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh6" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L365,40"/><path class="e" d="M384,59 L384,279"/><path class="e" d="M365,298 L59,298"/><path class="e" d="M40,279 L40,59"/><path class="e" d="M196.8,157.6 L55.2,51.4"/><path class="e" d="M227.2,157.6 L368.8,51.4"/><path class="e" d="M227.2,180.4 L368.8,286.6"/><path class="e" d="M196.8,180.4 L55.2,286.6"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="384" cy="40" r="18"/><text class="t" x="384" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="384" cy="298" r="18"/><text class="t" x="384" y="298" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="40" cy="298" r="18"/><text class="t" x="40" y="298" dy=".35em" text-anchor="middle">D</text><circle class="n" cx="212" cy="169" r="18"/><text class="t" x="212" y="169" dy=".35em" text-anchor="middle">O</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">5 vertices, 8 edges, 5 regions</figcaption></figure>

Six vertices, 12 edges. $r=2-6+12=8$. Since $3r\le2e$ gives $24\le24$, equality holds, so every region has exactly 3 edges.

==For a connected planar graph, $v-e+r=2$.==

Answer frame. Open with the definition and regions; state the formula and the induction proof; draw the wheel with regions numbered and verify $5-8+5=2$; for the 6-vertex question find $r=8$ then use $3r=2e$; close that every region is a triangle.

Asked: [7 marks] (Jun 2024, Dec 2024) Define planar graph. Prove that for any connected planar graph, $v-e+r=2$. Asked: [14 marks] (Jun 2020, Jun 2023) State Euler's formula for a planar graph. Give an example with 5 vertices and 5 regions and verify it. OR show that the maximum number of edges in a simple graph with $n$ vertices is $n(n-1)/2$. Asked: [7 marks] (Jun 2023) State Euler's formula for a planar graph. Give an example of a planar graph with 5 vertices and 5 regions and verify it. Asked: [7 marks] (Dec 2020) Show that in a connected planar graph with 6 vertices and 12 edges, each region is bounded by 3 edges.

Multigraphs and weighted graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A multigraph allows parallel edges between the same pair of vertices and may allow loops; a weighted graph attaches a number (weight, cost or length) to every edge.

Key points.

  1. Edges joining the same pair of vertices are parallel, and a loop joins a vertex to itself.
  2. A graph with no loops and no parallel edges is simple.
  3. The weight of a path is the sum of its edge weights, which shortest-path problems minimise.
  4. A minimal spanning tree is a spanning tree of least total weight, found by Prim's or Kruskal's algorithm; the height of a rooted tree is the length of its longest root-to-leaf path.
  5. If all edge weights are distinct, the maximal (and minimal) spanning tree is unique, because Kruskal or Prim never meets a tie. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-03" viewBox="0 0 338 80" width="338" height="80" role="img" aria-label="Multigraph with parallel edges"><style>#dsfig-u4-03 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-03 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-03 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-03 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-03 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-03 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-03 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-03 .t{fill:#16181D;font-weight:500}#dsfig-u4-03 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-03 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-03 .dot{fill:#16181D}#dsfig-u4-03 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-03 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-03 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-03 .ah{fill:#454C5A}#dsfig-u4-03 .ah.hi{fill:#2340B8}#dsfig-u4-03 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-03 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-03 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-03 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-03 .e{stroke:#B1B7C3}html.dark #dsfig-u4-03 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-03 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-03 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-03 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-03 .t{fill:#E6E8ED}html.dark #dsfig-u4-03 .t.inv{fill:#0F1115}html.dark #dsfig-u4-03 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-03 .dot{fill:#E6E8ED}html.dark #dsfig-u4-03 .ann{fill:#8FA3FF}html.dark #dsfig-u4-03 .lbl{fill:#858D9C}html.dark #dsfig-u4-03 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-03 .ah{fill:#B1B7C3}html.dark #dsfig-u4-03 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-03 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-03 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-03 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh7" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M59,40 L279,40"/><path class="e" d="M59,40 L279,40"/><g class="wl"><rect x="159.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">2</text></g><g class="wl"><rect x="159.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">5</text></g><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">B</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Multigraph with parallel edges</figcaption></figure>

Asked: [7 marks] (Jun 2020) Define with examples: i) Multigraph ii) Isomorphic graph iii) Eulerian graph. Asked: [7 marks] (Nov 2018) Define the following: i) Planar graph ii) Multigraph iii) Euler graph. Asked: [7 marks] (Nov 2022) Give a simple condition on the weights of a graph that guarantees a unique maximal spanning tree. Asked: [7 marks] (Jun 2024) Explain: i) Euler graph ii) Isomorphic graphs iii) Minimal spanning tree iv) Height of the tree.

Isomorphic graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. $G_1$ and $G_2$ are isomorphic if there is a bijection $f:V_1\to V_2$ with $(u,v)\in E_1\iff(f(u),f(v))\in E_2$, so adjacency and non-adjacency are preserved.

Key points.

  1. Isomorphic graphs are the same graph drawn differently.
  2. They have the same number of vertices and the same number of edges.
  3. They have the same degree sequence.
  4. They have the same cycle lengths and the same connectivity.
  5. Neighbours of corresponding vertices must have matching degrees.
  6. These conditions are necessary but not sufficient, so one mismatch proves non-isomorphism but equal counts prove nothing.
  7. Equivalently, the adjacency matrices become equal after the same relabelling of rows and columns.

Steps.

Step 1: Compare numbers of vertices and edges.
Step 2: Compare degree sequences.
Step 3: Compare cycle lengths, connectivity and adjacency of equal-degree vertices.
Step 4: Build a bijection f mapping vertices of equal degree.
Step 5: Check every edge maps to an edge; if all do, isomorphic, else not.

Example. The square $1\text{-}2\text{-}3\text{-}4\text{-}1$ and $a\text{-}c\text{-}b\text{-}d\text{-}a$ with $f:1\to a,2\to c,3\to b,4\to d$ both have 4 edges and degrees 2,2,2,2, and each edge maps to an edge, so they are isomorphic.

Non-isomorphic check (Dec 2023 figures). Both graphs have 8 vertices, 10 edges and degrees $3,3,3,3,2,2,2,2$. In $G_1$ the degree-3 vertices $A,H,F,C$ give only two disjoint edges $AH$, $FC$; in $G_2$ the degree-3 vertices $a,d,e,g$ form a 4-cycle. That invariant differs, so not isomorphic. Read the exact edges from the printed figure first.

<mark>Two graphs are isomorphic if a one-to-one onto vertex mapping preserves adjacency; equal vertices, edges and degree sequence are necessary but not sufficient.</mark>

Answer frame. Open with the bijection definition; give points 2 to 5 as the conditions and the five steps; for a figure tabulate vertices, edges and degrees, then write the bijection and verify every edge, or quote the failing invariant; close with the verdict.

Asked: [7 marks] (Nov 2018, Nov 2022) When can two graphs G1 and G2 be said to be isomorphic? Asked: [7 marks] (May 2019) Explain briefly: i) Isomorphic graph ii) Euler graph. Asked: [7 marks] (Jun 2020, Dec 2020, Dec 2023) Examine whether the given pairs of graphs G1 and G2 are isomorphic; prove that G and H are isomorphic. Asked: [7 marks] (Nov 2022, Jun 2025) Define isomorphism of graphs. What are the steps followed in discovering the isomorphism? Verify isomorphism between two adjacency matrices. Asked: [7 marks] (Dec 2023) Determine whether the graphs F1 and F2 are isomorphic.

Paths, cycles and connectivity

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A path is a sequence of distinct vertices with consecutive ones adjacent, a cycle is a closed path, and a graph is connected if every two vertices are joined by a path.

Key points.

  1. A walk may repeat vertices and edges, a trail repeats no edge, and a path repeats no vertex.
  2. A disconnected graph splits into components, the maximal connected subgraphs.
  3. A bridge is an edge whose removal increases the number of components.
  4. A connected graph on $n$ vertices has at least $n-1$ edges.

Theorem. A simple graph with $n$ vertices and $k$ components has at most $\frac{(n-k)(n-k+1)}2$ edges. Proof. Let component sizes be $n_1,\dots,n_k$ with $\sum n_i=n$. Edges are maximum when each component is complete, giving $\sum\frac{n_i(n_i-1)}2$. If $n_1\ge n_2>1$, moving one vertex from component 2 to 1 changes the total by $n_1-(n_2-1)>0$, so the maximum has $k-1$ isolated vertices and one component of $n-k+1$ vertices. Edges $=\frac{(n-k+1)(n-k)}2$. $\blacksquare$

Asked: [7 marks] (Dec 2020) Prove that the maximum number of edges in a simple disconnected graph G with n vertices and k components is $\frac{(n-k)(n-k+1)}{2}$.

Shortest path in weighted graph

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. The shortest path from $a$ to $z$ is the path of least total edge weight; Dijkstra's algorithm finds it when all weights are non-negative.

Algorithm (Dijkstra).

Step 1: Set dist(a)=0 and dist(v)=infinity for all other v; mark all unvisited.
Step 2: Pick the unvisited vertex u with least dist and mark it visited.
Step 3: For each unvisited neighbour v, if dist(u)+w(u,v) < dist(v), set dist(v) to it and record u as predecessor (relaxation).
Step 4: Repeat from Step 2 until z is visited.
Step 5: Trace predecessors back from z; dist(z) is the length.

Key points.

  1. Dijkstra is greedy: the unvisited vertex with least distance cannot be improved, as weights are non-negative.
  2. Negative weights break it, so Bellman-Ford is used instead.
  3. Time is $O(n^2)$ with an adjacency matrix and $O((n+e)\log n)$ with a heap.
  4. It stops when the target is visited, and the predecessors give the path.

Example. Weights $ab=3,ac=6,bc=4,bd=7,be=9,ce=5,de=4,dz=6,ez=8$. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-04" viewBox="0 0 510 252" width="510" height="252" role="img" aria-label="Shortest path a-b-d-z"><style>#dsfig-u4-04 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-04 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-04 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-04 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-04 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-04 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-04 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-04 .t{fill:#16181D;font-weight:500}#dsfig-u4-04 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-04 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-04 .dot{fill:#16181D}#dsfig-u4-04 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-04 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-04 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-04 .ah{fill:#454C5A}#dsfig-u4-04 .ah.hi{fill:#2340B8}#dsfig-u4-04 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-04 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-04 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-04 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-04 .e{stroke:#B1B7C3}html.dark #dsfig-u4-04 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-04 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-04 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-04 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-04 .t{fill:#E6E8ED}html.dark #dsfig-u4-04 .t.inv{fill:#0F1115}html.dark #dsfig-u4-04 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-04 .dot{fill:#E6E8ED}html.dark #dsfig-u4-04 .ann{fill:#8FA3FF}html.dark #dsfig-u4-04 .lbl{fill:#858D9C}html.dark #dsfig-u4-04 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-04 .ah{fill:#B1B7C3}html.dark #dsfig-u4-04 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-04 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-04 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-04 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh8" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e hi" d="M55.8,115.5 L153.2,50.5"/><path class="e" d="M55.8,136.5 L153.2,201.5"/><path class="e" d="M169,59 L169,193"/><path class="e hi" d="M188,40 L322,40"/><path class="e" d="M182.4,53.4 L327.6,198.6"/><path class="e" d="M188,212 L322,212"/><path class="e" d="M341,59 L341,193"/><path class="e hi" d="M356.8,50.5 L454.2,115.5"/><path class="e" d="M356.8,201.5 L454.2,136.5"/><g class="wl hi"><rect x="94.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="83" dy=".35em" text-anchor="middle">3</text></g><g class="wl"><rect x="94.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="104.5" y="169" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="159.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">4</text></g><g class="wl hi"><rect x="245.4" y="31" width="19.2" height="18" rx="9"/><text class="t" x="255" y="40" dy=".35em" text-anchor="middle">7</text></g><g class="wl"><rect x="245.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="255" y="126" dy=".35em" text-anchor="middle">9</text></g><g class="wl"><rect x="245.4" y="203" width="19.2" height="18" rx="9"/><text class="t" x="255" y="212" dy=".35em" text-anchor="middle">5</text></g><g class="wl"><rect x="331.4" y="117" width="19.2" height="18" rx="9"/><text class="t" x="341" y="126" dy=".35em" text-anchor="middle">4</text></g><g class="wl hi"><rect x="395.9" y="74" width="19.2" height="18" rx="9"/><text class="t" x="405.5" y="83" dy=".35em" text-anchor="middle">6</text></g><g class="wl"><rect x="395.9" y="160" width="19.2" height="18" rx="9"/><text class="t" x="405.5" y="169" dy=".35em" text-anchor="middle">8</text></g><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">a</text><circle class="n" cx="169" cy="40" r="18"/><text class="t" x="169" y="40" dy=".35em" text-anchor="middle">b</text><circle class="n" cx="169" cy="212" r="18"/><text class="t" x="169" y="212" dy=".35em" text-anchor="middle">c</text><circle class="n" cx="341" cy="40" r="18"/><text class="t" x="341" y="40" dy=".35em" text-anchor="middle">d</text><circle class="n" cx="341" cy="212" r="18"/><text class="t" x="341" y="212" dy=".35em" text-anchor="middle">e</text><circle class="n" cx="470" cy="126" r="18"/><text class="t" x="470" y="126" dy=".35em" text-anchor="middle">z</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Shortest path a-b-d-z</figcaption></figure>

Settled b c d e z
a (0) 3 6 inf inf inf
b (3) 3 6 10 12 inf
c (6) 3 6 10 11 inf
d (10) 3 6 10 11 16

Then $e$ (11) leaves $z=16$. Other routes: $a\text{-}c\text{-}e\text{-}z=19$, $a\text{-}b\text{-}e\text{-}z=20$. Shortest path $a\to b\to d\to z$, length 16. The other printed graphs use the same method with their weights.

<mark>Dijkstra's algorithm repeatedly settles the unvisited vertex of least tentative distance and relaxes its edges, and works only for non-negative weights.</mark>

Answer frame. Open with the definition and the non-negative condition; write the five steps; draw the graph and fill the distance table; close with the path, its length and $O(n^2)$. For "write an algorithm" the steps, complexity and stopping rule suffice.

Asked: [7 marks] (Nov 2018, May 2019, Jun 2020) Determine the shortest path between vertices a and z in the graph. Asked: [7 marks] (May 2019) Write an algorithm to find the shortest path in a weighted graph. Asked: [7 marks] (Dec 2025) Explain Dijkstra's algorithm and find the shortest path from a given source vertex in a weighted graph.

Eulerian paths and circuits

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. An Euler path uses every edge exactly once; an Euler circuit is a closed Euler path; a connected graph with an Euler circuit is an Euler graph.

Theorem. A connected graph is an Euler graph iff every vertex has even degree. Necessity. In an Euler circuit each visit to a vertex enters by one edge and leaves by another, so its edges pair up and the degree is even. Sufficiency (induction on edges). All degrees are at least 2, so $G$ has a cycle $C$. Delete $C$'s edges: degrees stay even and each remaining component has an Euler circuit by hypothesis. Walk along $C$ and splice each component's circuit in at a shared vertex, giving one closed trail through all edges. $\blacksquare$

Key points.

  1. An Euler circuit exists iff the graph is connected and has no odd-degree vertex.
  2. An Euler path that is not a circuit exists iff it is connected with exactly 2 odd vertices, and it runs from one to the other.
  3. With more than 2 odd vertices there is neither, and the number of odd vertices is always even.
  4. A connected digraph has an Euler circuit iff in-degree equals out-degree at every vertex.
  5. A complete digraph has a directed edge in each direction between every pair of vertices, so it has $n(n-1)$ edges and in-degree $=$ out-degree $=n-1$, hence it is Eulerian.
  6. Fleury's algorithm builds the trail by never crossing a bridge of the remaining graph unless forced. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-05" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="Complete digraph on 3 vertices"><style>#dsfig-u4-05 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-05 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-05 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-05 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-05 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-05 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-05 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-05 .t{fill:#16181D;font-weight:500}#dsfig-u4-05 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-05 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-05 .dot{fill:#16181D}#dsfig-u4-05 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-05 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-05 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-05 .ah{fill:#454C5A}#dsfig-u4-05 .ah.hi{fill:#2340B8}#dsfig-u4-05 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-05 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-05 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-05 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-05 .e{stroke:#B1B7C3}html.dark #dsfig-u4-05 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-05 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-05 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-05 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-05 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-05 .t{fill:#E6E8ED}html.dark #dsfig-u4-05 .t.inv{fill:#0F1115}html.dark #dsfig-u4-05 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-05 .dot{fill:#E6E8ED}html.dark #dsfig-u4-05 .ann{fill:#8FA3FF}html.dark #dsfig-u4-05 .lbl{fill:#858D9C}html.dark #dsfig-u4-05 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-05 .ah{fill:#B1B7C3}html.dark #dsfig-u4-05 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-05 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-05 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-05 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh9" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M54.8,197.2 L197.2,54.8" marker-end="url(#ah9)" marker-start="url(#ah9)"/><path class="e" d="M226.8,54.8 L369.2,197.2" marker-end="url(#ah9)" marker-start="url(#ah9)"/><path class="e" d="M363,212 L61,212" marker-end="url(#ah9)" marker-start="url(#ah9)"/><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Q</text><circle class="n" cx="384" cy="212" r="18"/><text class="t" x="384" y="212" dy=".35em" text-anchor="middle">R</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Complete digraph on 3 vertices</figcaption></figure>

Example (Jun 2025). $E=\{AB,BC,CD,DA,AC\}$: degrees $A=3,B=2,C=3,D=2$. Exactly two are odd, so an Euler path exists but no Euler circuit, e.g. $A\text{-}B\text{-}C\text{-}A\text{-}D\text{-}C$. The only Hamiltonian circuit is $A\text{-}B\text{-}C\text{-}D\text{-}A$ and its reverse, since $B$ and $D$ each force both their edges. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-06" viewBox="0 0 424 252" width="424" height="252" role="img" aria-label="deg A=3, B=2, C=3, D=2"><style>#dsfig-u4-06 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-06 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-06 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-06 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-06 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-06 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-06 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-06 .t{fill:#16181D;font-weight:500}#dsfig-u4-06 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-06 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-06 .dot{fill:#16181D}#dsfig-u4-06 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-06 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-06 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-06 .ah{fill:#454C5A}#dsfig-u4-06 .ah.hi{fill:#2340B8}#dsfig-u4-06 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-06 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-06 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-06 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-06 .e{stroke:#B1B7C3}html.dark #dsfig-u4-06 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-06 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-06 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-06 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-06 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-06 .t{fill:#E6E8ED}html.dark #dsfig-u4-06 .t.inv{fill:#0F1115}html.dark #dsfig-u4-06 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-06 .dot{fill:#E6E8ED}html.dark #dsfig-u4-06 .ann{fill:#8FA3FF}html.dark #dsfig-u4-06 .lbl{fill:#858D9C}html.dark #dsfig-u4-06 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-06 .ah{fill:#B1B7C3}html.dark #dsfig-u4-06 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-06 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-06 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-06 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh10" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M57,117.5 L195,48.5"/><path class="e" d="M229,48.5 L367,117.5"/><path class="e" d="M367,134.5 L229,203.5"/><path class="e" d="M195,203.5 L57,134.5"/><path class="e" d="M59,126 L365,126"/><circle class="n" cx="40" cy="126" r="18"/><text class="t" x="40" y="126" dy=".35em" text-anchor="middle">A</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">B</text><circle class="n" cx="384" cy="126" r="18"/><text class="t" x="384" y="126" dy=".35em" text-anchor="middle">C</text><circle class="n" cx="212" cy="212" r="18"/><text class="t" x="212" y="212" dy=".35em" text-anchor="middle">D</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">deg A=3, B=2, C=3, D=2</figcaption></figure>

Example (Dec 2023). Edges $AB,BC,CD,DA,AG,GF,FE,EC,CF,FA$ give degrees $A=4,B=2,C=4,D=2,E=2,F=4,G=2$, all even. Trail: $A\text{-}B\text{-}C\text{-}D\text{-}A\text{-}G\text{-}F\text{-}E\text{-}C\text{-}F\text{-}A$ uses all 10 edges once.

<mark>A connected graph has an Euler circuit iff all its vertices have even degree, and an Euler path iff it has exactly 0 or 2 odd vertices.</mark>

Answer frame. Open with the definitions; state both degree conditions; for the theorem give necessity then sufficiency; for a figure tabulate degrees, name the odd vertices and write the vertex sequence; for complete digraph draw $K_3$ with arrows; close with the verdict.

Asked: [7 marks] (Jun 2024, Dec 2024) Discuss complete digraph and Euler graph with suitable examples. Asked: [7 marks] (Nov 2019) Prove that a connected graph G is an Euler graph iff every vertex of G is of even degree. Asked: [7 marks] (Dec 2023) Find an Euler path in the graph below. Asked: [7 marks] (Jun 2025) For G with V={A,B,C,D} and E={AB,BC,CD,DA,AC}, determine i) whether it has an Eulerian path or circuit, ii) all Hamiltonian circuits. Asked: [7 marks] (Dec 2025) Define Euler path and Euler circuit. State necessary and sufficient conditions for their existence.

Hamiltonian paths and circuits

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A Hamiltonian path visits every vertex exactly once, and a Hamiltonian circuit is a closed one.

Key points.

  1. No simple necessary and sufficient condition is known for Hamiltonian graphs.
  2. Dirac's theorem: a simple graph with $n\ge3$ vertices and every degree at least $n/2$ is Hamiltonian.
  3. $K_n$ has $(n-1)!/2$ Hamiltonian circuits, so $K_5$ has 12.
  4. The bow-tie (two triangles sharing a vertex) is Eulerian but not Hamiltonian; $K_4$ (all degrees 3) is Hamiltonian but not Eulerian. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-07" viewBox="0 0 338 252" width="338" height="252" role="img" aria-label="Bow-tie, Eulerian but not Hamiltonian"><style>#dsfig-u4-07 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-07 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-07 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-07 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-07 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-07 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-07 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-07 .t{fill:#16181D;font-weight:500}#dsfig-u4-07 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-07 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-07 .dot{fill:#16181D}#dsfig-u4-07 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-07 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-07 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-07 .ah{fill:#454C5A}#dsfig-u4-07 .ah.hi{fill:#2340B8}#dsfig-u4-07 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-07 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-07 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-07 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-07 .e{stroke:#B1B7C3}html.dark #dsfig-u4-07 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-07 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-07 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-07 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-07 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-07 .t{fill:#E6E8ED}html.dark #dsfig-u4-07 .t.inv{fill:#0F1115}html.dark #dsfig-u4-07 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-07 .dot{fill:#E6E8ED}html.dark #dsfig-u4-07 .ann{fill:#8FA3FF}html.dark #dsfig-u4-07 .lbl{fill:#858D9C}html.dark #dsfig-u4-07 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-07 .ah{fill:#B1B7C3}html.dark #dsfig-u4-07 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-07 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-07 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-07 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh11" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M40,59 L40,193"/><path class="e" d="M55.8,50.5 L153.2,115.5"/><path class="e" d="M55.8,201.5 L153.2,136.5"/><path class="e" d="M184.8,115.5 L282.2,50.5"/><path class="e" d="M184.8,136.5 L282.2,201.5"/><path class="e" d="M298,59 L298,193"/><circle class="n" cx="40" cy="40" r="18"/><text class="t" x="40" y="40" dy=".35em" text-anchor="middle">X</text><circle class="n" cx="40" cy="212" r="18"/><text class="t" x="40" y="212" dy=".35em" text-anchor="middle">Y</text><circle class="n" cx="169" cy="126" r="18"/><text class="t" x="169" y="126" dy=".35em" text-anchor="middle">M</text><circle class="n" cx="298" cy="40" r="18"/><text class="t" x="298" y="40" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="298" cy="212" r="18"/><text class="t" x="298" y="212" dy=".35em" text-anchor="middle">Q</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Bow-tie, Eulerian but not Hamiltonian</figcaption></figure>

Minimal circuit (Jun 2023). Weights $AB=100,BC=125,CD=300,DE=75,EA=175,AC=200,BD=275,CE=150,AD=225,BE=250$. Of the 12 circuits:

Circuit Weight
A-B-C-D-E-A 775
A-B-C-E-D-A 100+125+150+75+225 = 675
A-B-D-E-C-A 800
A-C-B-D-E-A 850

Minimal circuit $A\to B\to C\to E\to D\to A$, weight 675 (the next best is 775).

Asked: [7 marks] (Jun 2023) Find a Hamiltonian circuit of minimal weight in the complete weighted graph on 5 vertices. Asked: [7 marks] (Nov 2022) Explain Eulerian and Hamiltonian graphs with examples; draw i) Eulerian but not Hamiltonian ii) Hamiltonian but not Eulerian.

Graph coloring and chromatic number

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">High weight</span>

Definition. Graph colouring assigns colours to vertices so that adjacent vertices get different colours; the chromatic number $\chi(G)$ is the least number of colours that suffices.

Diagram. <figure class="ds-fig" style="margin:1.4rem 0;overflow-x:auto"><svg xmlns="http://www.w3.org/2000/svg" id="dsfig-u4-08" viewBox="0 0 424 338" width="424" height="338" role="img" aria-label="Triangle PQR needs 3 colours; S reuses the colour of P; chi=3"><style>#dsfig-u4-08 .e{stroke:#454C5A;stroke-width:1.4;fill:none}#dsfig-u4-08 .e.hi{stroke:#2340B8;stroke-width:2.6}#dsfig-u4-08 .n{fill:#FFFFFF;stroke:#16181D;stroke-width:1.4}#dsfig-u4-08 .n.hi{fill:#E3E9FC;stroke:#2340B8;stroke-width:2.2}#dsfig-u4-08 .n.rb-b{fill:#16181D;stroke:#16181D}#dsfig-u4-08 .n.rb-r{fill:#BD3227;stroke:#BD3227}#dsfig-u4-08 text{font-family:"JetBrains Mono",ui-monospace,Menlo,Consolas,monospace;font-size:13px}#dsfig-u4-08 .t{fill:#16181D;font-weight:500}#dsfig-u4-08 .t.inv{fill:#FFFFFF;font-weight:700}#dsfig-u4-08 .kd{stroke:#16181D;stroke-width:1.2}#dsfig-u4-08 .dot{fill:#16181D}#dsfig-u4-08 .ann{fill:#2340B8;font-size:11px;font-weight:700}#dsfig-u4-08 .lbl{fill:#6F7787;font-family:system-ui,-apple-system,sans-serif;font-size:12px;font-weight:700}#dsfig-u4-08 .ptr{fill:#2340B8;font-size:12px;font-weight:700}#dsfig-u4-08 .ah{fill:#454C5A}#dsfig-u4-08 .ah.hi{fill:#2340B8}#dsfig-u4-08 .wl rect{fill:#FFFFFF;stroke:#DCE0E7}#dsfig-u4-08 .wl .t{font-size:12px;font-weight:700}#dsfig-u4-08 .wl.hi rect{fill:#2340B8;stroke:#2340B8}#dsfig-u4-08 .wl.hi .t{fill:#FFFFFF}html.dark #dsfig-u4-08 .e{stroke:#B1B7C3}html.dark #dsfig-u4-08 .e.hi{stroke:#8FA3FF}html.dark #dsfig-u4-08 .n{fill:#161920;stroke:#E6E8ED}html.dark #dsfig-u4-08 .n.hi{fill:#1E2748;stroke:#8FA3FF}html.dark #dsfig-u4-08 .n.rb-b{fill:#E6E8ED;stroke:#E6E8ED}html.dark #dsfig-u4-08 .n.rb-r{fill:#FF7E71;stroke:#FF7E71}html.dark #dsfig-u4-08 .t{fill:#E6E8ED}html.dark #dsfig-u4-08 .t.inv{fill:#0F1115}html.dark #dsfig-u4-08 .kd{stroke:#E6E8ED}html.dark #dsfig-u4-08 .dot{fill:#E6E8ED}html.dark #dsfig-u4-08 .ann{fill:#8FA3FF}html.dark #dsfig-u4-08 .lbl{fill:#858D9C}html.dark #dsfig-u4-08 .ptr{fill:#8FA3FF}html.dark #dsfig-u4-08 .ah{fill:#B1B7C3}html.dark #dsfig-u4-08 .ah.hi{fill:#8FA3FF}html.dark #dsfig-u4-08 .wl rect{fill:#161920;stroke:#2A2E37}html.dark #dsfig-u4-08 .wl.hi rect{fill:#8FA3FF;stroke:#8FA3FF}html.dark #dsfig-u4-08 .wl.hi .t{fill:#0F1115}</style><defs><marker id="ah12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah" d="M0,1 L9,5 L0,9 z"/></marker><marker id="ahh12" viewBox="0 0 10 10" refX="9" refY="5" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path class="ah hi" d="M0,1 L9,5 L0,9 z"/></marker></defs><path class="e" d="M55.2,157.6 L196.8,51.4"/><path class="e" d="M55.2,180.4 L196.8,286.6"/><path class="e" d="M212,59 L212,279"/><path class="e" d="M227.2,51.4 L368.8,157.6"/><path class="e" d="M227.2,286.6 L368.8,180.4"/><circle class="n" cx="40" cy="169" r="18"/><text class="t" x="40" y="169" dy=".35em" text-anchor="middle">P</text><circle class="n" cx="212" cy="40" r="18"/><text class="t" x="212" y="40" dy=".35em" text-anchor="middle">Q</text><circle class="n" cx="212" cy="298" r="18"/><text class="t" x="212" y="298" dy=".35em" text-anchor="middle">R</text><circle class="n" cx="384" cy="169" r="18"/><text class="t" x="384" y="169" dy=".35em" text-anchor="middle">S</text></svg><figcaption style="font-size:.82em;opacity:.72;margin-top:.45rem">Triangle PQR needs 3 colours; S reuses the colour of P; chi=3</figcaption></figure>

Key points.

  1. A graph with an edge needs at least 2 colours, and $\chi=1$ only for an edgeless graph.
  2. $\chi(K_n)=n$, since every vertex is adjacent to all others, so a triangle needs 3.
  3. A graph is bipartite iff $\chi\le2$, so trees, $K_{2,2}$ and even cycles need 2.
  4. An odd cycle needs 3 colours.
  5. $\chi(G)\le\Delta(G)+1$, where $\Delta$ is the maximum degree.
  6. Four Colour Theorem: every planar graph, hence every map, needs at most 4 colours.
  7. Applications: timetabling and exam scheduling (courses are vertices, clashes are edges, colours are slots); register allocation in compilers; map colouring; frequency assignment to radio or mobile towers within interference range.

<mark>The chromatic number of a graph is the smallest number of colours that can be assigned to its vertices so that adjacent vertices have different colours.</mark>

Answer frame. Open with proper colouring and $\chi(G)$; draw the coloured graph with colours beside vertices and $\chi=3$; quote the $K_n$, bipartite and odd-cycle values; for applications give timetabling, register allocation, map colouring, frequency assignment in one sentence each; close with the Four Colour Theorem.

Asked: [7 marks] (May 2019, Jun 2020) What is graph coloring? Define chromatic number. Give any one example. Asked: [14 marks] (Jun 2020) Write short notes (any two): a) Graph Coloring (b to e belong to other units). Asked: [7 marks] (Jun 2023) Discuss the various applications of graph colouring.

Isomorphism and homomorphism of graphs

<span style="display:inline-block;padding:.16em .6em;border:1.5px solid currentColor;border-radius:999px;font-size:.68em;font-weight:700;letter-spacing:.06em;text-transform:uppercase;opacity:.75">Low weight</span>

Definition. A graph homomorphism is a vertex map that sends every edge to an edge, without needing to be one-to-one; an isomorphism is a bijective one whose inverse also preserves edges. The complement $\bar G$ has the same vertices and exactly the edges $G$ lacks, and $G$ is self-complementary if $G\cong\bar G$.

Key points.

  1. Every isomorphism is a homomorphism, but a homomorphism can merge vertices.
  2. A proper $k$-colouring is a homomorphism into $K_k$.
  3. $G$ and $\bar G$ together have all $\frac{n(n-1)}2$ edges of $K_n$.
  4. A self-complementary graph has equal numbers of edges in $G$ and $\bar G$.

Theorem. A self-complementary graph has $n\equiv0$ or $1\pmod4$ vertices. Proof. With $m$ edges in $G$ and in $\bar G$, $2m=\frac{n(n-1)}2$, so $m=\frac{n(n-1)}4$ is an integer and $4\mid n(n-1)$. The numbers $n$ and $n-1$ are consecutive, so one is odd and the other is divisible by 4. Hence $n\equiv0$ or $1\pmod 4$. $\blacksquare$

Asked: [7 marks] (Dec 2020) If G is a self-complementary graph, then prove that G has $n\equiv0$ (or) $1 \pmod 4$ vertices.

Last-minute revision

  • Handshaking: $\sum\deg=2|E|$; odd-degree vertices are even in number; degrees 1,3,4,2,3 sum to 13, impossible.
  • $K_n$ has $\frac{n(n-1)}2$ edges; a regular binary tree has $2i+1$ vertices.
  • Euler's formula $v-e+r=2$; simple planar $3r\le2e$; $K_5$, $K_{3,3}$ non-planar.
  • 5 vertices, 5 regions gives $e=8$; 6 vertices, 12 edges gives $r=8$, all triangles.
  • Isomorphism: bijection preserving adjacency; test vertices, edges, degrees, cycles, then map.
  • Dijkstra: non-negative weights, $O(n^2)$; a to z answer $a\text{-}b\text{-}d\text{-}z=16$.
  • Euler circuit: connected, all degrees even; Euler path: exactly 2 odd vertices.
  • Jun 2025 graph: Euler path $A\text{-}B\text{-}C\text{-}A\text{-}D\text{-}C$, Hamiltonian $A\text{-}B\text{-}C\text{-}D\text{-}A$.
  • $K_5$ minimal Hamiltonian circuit $A\text{-}B\text{-}C\text{-}E\text{-}D\text{-}A=675$.
  • $\chi(K_n)=n$, bipartite 2, odd cycle 3; four colours suffice for planar graphs.
  • Disconnected with $k$ components: at most $\frac{(n-k)(n-k+1)}2$ edges; self-complementary: $n\equiv0,1\pmod4$.

Memory hooks

  • Handshake: every edge shakes two hands, so degrees total $2e$.
  • Euler formula: $v-e+r=2$, and count the outer region.
  • Euler is Even degrees on Edges; Hamilton visits Houses (vertices) once.
  • Dijkstra: settle the nearest, relax the neighbours, no negative weights.
  • Colouring: clash graph, colours are slots; triangle needs 3.

Coverage checklist

  • Introduction and basic terminology of graphs: Dec 2024, Nov 2019 (two), Nov 2022, Jun 2025.
  • Planer graphs: Jun 2024/Dec 2024, Jun 2020/Jun 2023, Jun 2023, Dec 2020.
  • Multigraphs and weighted graphs: Jun 2020, Nov 2018, Nov 2022, Jun 2024.
  • Isomorphic graphs: Nov 2018/Nov 2022, May 2019, Jun 2020/Dec 2020/Dec 2023, Nov 2022/Jun 2025, Dec 2023.
  • Paths, Cycles and connectivity: Dec 2020.
  • Shortest path in weighted graph: Nov 2018/May 2019/Jun 2020, May 2019, Dec 2025.
  • Introduction to Eulerian paths and circuits: Jun 2024/Dec 2024, Nov 2019, Dec 2023, Jun 2025, Dec 2025.
  • Hamiltonian paths and circuits: Jun 2023, Nov 2022.
  • Graph coloring, chromatic number: May 2019/Jun 2020, Jun 2020, Jun 2023.
  • Isomorphism and Homomorphism of graphs: Dec 2020.
Go to where you left off?

Quick Add to Notes

Save questions, your own notes and screenshots into notes filed by unit. It takes a free account.

Create free account

Have an account? Log in