What are common examiner traps in Graph Theory?

Forgetting to include the source vertex s in the final summation Evaluating vertices out of topological order, leading to incorrect maximal values when multiple paths merge Adding edge weights instead of multiplying them according to the defined path metric rule Arithmetic errors when computing intermediate products with large weight multipliers Confusing the Hamiltonian cycle requirement (visiting every vertex exactly once) with Eulerian circuit (visiting every edge exactly once). Assuming a graph is Hamiltonian merely because it is 2-connected, ignoring forced smaller cycles created by multiple degree-2 vertices sharing identical neighbor sets. Forgetting that an odd number of vertices in a bipartite or grid graph prohibits a Hamiltonian cycle. Assuming |E| n - 1 guarantees acyclicity without confirming connectivity (e.g., disjoint union of C3 and an isolated vertex has |E| = 3 4 - 1 but contains a cycle). Assuming minimum degree 1 (at least one non-zero entry in each row/column) implies graph connectivity (e.g., K2 K2 is disconnected). Assuming odd/even walk parity reachability ensures all entries in An-1 + In are non-zero for connected bipartite graphs. Confusing the general upper bound of planar vertex colouring (4) with specific planar sub-classes like triangle-free (3) or bipartite planar (2). Confusing vertex overlap with edge overlap (spanning trees always share all n vertices, but their edge sets can be completely disjoint). Assuming two spanning trees must share at least one edge even when n 4. Ignoring constraints on n (e.g., n > 4) which guarantee the existence of edge-disjoint spanning trees. Confusing Hamiltonian Path (visiting all vertices without closing) with Hamiltonian Cycle (closed tour), especially on the Petersen graph. Assuming the greedy coloring algorithm always uses exactly the minimum number of colors (G) (greedy coloring is order-dependent and can require up to + 1). Off-by-one errors when applying Euler's formula n - m + f = 1 + k versus n - m + f = 2 on disconnected or multi-component graphs. Forgetting that Cayley's formula nn-2 applies strictly to labeled trees, not unlabeled isomorphism classes. Assuming maximum independent set size (G) equals n/2 or 3 on Petersen graph instead of the correct value 4. Confusing the number of edges in the original graph G with the number of edges in the DFS spanning forest EF. Off-by-one errors by assuming the graph is fully connected (EF = n - 1) instead of accounting for multiple disjoint components (EF = n - k). Incorrectly adding k instead of subtracting k in EF = n - k, leading to n + EF or other arithmetic missteps. Confusing total faces F with bounded interior faces (Fbounded = F - 1). Assuming (G) = k implies the presence of a complete subgraph Kk (cliques imply high chromatic number, but high chromatic number does not imply a clique, e.g., C5). Forgetting that each 3-cycle is counted 6 times in trace(A3) due to 3 starting vertices and 2 traversal directions. Neglecting isolated vertices (di = 0) during manual graphic sequence reductions. Assuming every graph with (G) = k must have a vertex with degree k, rather than degree k - 1.

Graph Theory

21 Qs · since 2012 · 38 marks · 1.5 marks/paperMedium yield

Take topic test

In GATE CS, graph theory under Engineering Mathematics emphasizes structural properties, algebraic relationships, and topological invariants of simple undirected graphs. Questions… Guide

Type

GATE CSE 2026 Set 2Q8MCQ2 marksMediumDiagramFigures (i) and (ii) represent intercity highway systems. The black dots represent cities and the line segments between them represent intercity highways. A salesperson needs to make a trip. She needs to start from a city, visit each of the remaining cities exactly once, and finally return to the same city from which…
GATE CSE 2026 Set 2Q36MCQ2 marksEasyConsider a complete graph $K_n$ with $n$ vertices ( $n > 4$ ). Note that multiple spanning trees can be constructed over $K_n$ . Each of these spanning trees is represented as a set of edges. The Jaccard coefficient between any two sets is defined as the ratio of the size of the intersection of the two sets to…
GATE CSE 2024 Set 1Q34NAT1 markEasyThe number of spanning trees in a complete graph of 4 vertices labelled A, B, C, and D is ________
GATE CSE 2024 Set 1Q51MSQ2 marksMediumThe chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$ . Which of the following statements is/are always TRUE?
GATE CSE 2024 Set 1Q60NAT2 marksEasyThe number of edges present in the forest generated by the DFS traversal of an undirected graph $G$ with 100 vertices is 40. The number of connected components in $G$ is ________
GATE CSE 2024 Set 2Q60NAT2 marksEasyDiagramThe chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph is ________
GATE CSE 2023Q55MSQ2 marksMediumLet $G$ be a simple, finite, undirected graph with vertex set $\{v_1, \ldots, v_n\}$ . Let $\Delta(G)$ denote the maximum degree of $G$ and let $\mathbb{N} = \{1, 2, \ldots\}$ denote the set of all possible colors. Color the vertices of $G$ using the following greedy strategy: for $i = 1, \ldots, n$ $\text{color}(v_i) \leftarrow \min\{j \in \mathbb{N} : \text{ no neighbour of } v_i \text{ is colored } j\}$ …
GATE CSE 2022Q37MCQ2 marksEasyConsider a simple undirected unweighted graph with at least three vertices. If $A$ is the adjacency matrix of the graph, then the number of 3-cycles in the graph is given by the trace of
GATE CSE 2022Q50MSQ2 marksMediumDiagramThe following simple undirected graph is referred to as the Peterson graph. Which of the following statements is/are TRUE?
GATE CSE 2022Q52MSQ2 marksMediumWhich of the properties hold for the adjacency matrix $A$ of a simple undirected unweighted graph having $n$ vertices?
GATE CSE 2021 Set 1Q16NAT1 markEasyIn an undirected connected planar graph $G$ , there are eight vertices and five faces. The number of edges in $G$ is _________.
GATE CSE 2021 Set 2Q55NAT2 marksMediumDiagramIn a directed acyclic graph with a source vertex $\mathbf{s}$ , the *quality-score* of a directed path is defined to be the product of the weights of the edges on the path. Further, for a vertex $v$ other than $\mathbf{s}$ , the quality-score of $v$ is defined to be the maximum among the quality-scores of all…
GATE CSE 2020Q52NAT2 marksMediumGraph $G$ is obtained by adding vertex $s$ to $K_{3,4}$ and making $s$ adjacent to every vertex of $K_{3,4}$ . The minimum number of colours required to edge-colour $G$ is _______.
GATE CSE 2016 Set 2Q3NAT1 markEasyThe minimum number of colours that is sufficient to vertex-colour any planar graph is ________.
GATE CSE 2015 Set 1Q54NAT2 marksEasyLet $G$ be a connected planar graph with 10 vertices. If the number of edges on each face is three, then the number of edges in $G$ is ____________.
GATE CSE 2014 Set 1Q51NAT2 marksMediumConsider an undirected graph $G$ where self-loops are not allowed. The vertex set of $G$ is $\{(i,j): 1 \le i \le 12, 1 \le j \le 12\}$ . There is an edge between $(a,b)$ and $(c,d)$ if $|a - c| \le 1$ and $|b - d| \le 1$ . The number of edges in this graph is _______.
GATE CSE 2014 Set 1Q52MCQ2 marksMediumAn ordered $n$ -tuple $(d_1, d_2, ..., d_n)$ with $d_1 \ge d_2 \ge \dots \ge d_n$ is called *graphic* if there exists a simple undirected graph with $n$ vertices having degrees $d_1, d_2, ..., d_n$ respectively. Which of the following 6-tuples is NOT graphic?
GATE CSE 2014 Set 2Q51NAT2 marksEasyA cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is $\underline{\hspace{1cm}}$ .
GATE CSE 2014 Set 3Q51MCQ2 marksEasyIf $G$ is a forest with $n$ vertices and $k$ connected components, how many edges does $G$ have?
GATE CSE 2014 Set 3Q52MCQ2 marksMediumLet $\delta$ denote the minimum degree of a vertex in a graph. For all planar graphs on $n$ vertices with $\delta \ge 3$ , which one of the following is TRUE?
GATE CSE 2012Q17MCQ1 markEasyLet G be a simple undirected planar graph on 10 vertices with 15 edges. If G is a connected graph, then the number of bounded faces in any embedding of G on the plane is equal to

Topic guide

What does GATE test in Graph Theory?

In GATE CS, graph theory under Engineering Mathematics emphasizes structural properties, algebraic relationships, and topological invariants of simple undirected graphs. Questions frequently evaluate planar graph relationships using Euler's formula, chromatic numbers and edge coloring bounds (Vizing's theorem, independent set bounds), and degree-based properties (Handshaking lemma, Havel-Hakimi theorem). The focus has steadily migrated from direct formula applications to structural reasoning and algebraic characterizations such as matrix powers.

Core concepts

Directed Acyclic Graphs (DAGs)
Topological sorting / topological traversal order
Dynamic programming on DAGs
Path product optimization
Source-to-vertex reachable paths
Hamiltonian cycle existence and structural necessary conditions
Edge-forcing from low-degree vertices (degree-2 vertices forcing both incident edges)
Subcycle elimination / premature cycle closure
Grid graph (Pm Pn) Hamiltonicity
Distinction between Hamiltonian cycle (vertex-traversal) and Eulerian circuit (edge-traversal)
Planar graph vertex colouring and chromatic number
Adjacency matrix representation of simple undirected graphs
Powers of adjacency matrices and walk counts (Ak)
Graph connectivity and degree constraints
Acyclicity vs edge count bounds (|E| n-1)
Properties of complete graphs Kn
Edge count and structure of spanning trees (n-1 edges)
Edge-disjoint spanning trees (spanning tree packing)
Jaccard similarity coefficient applied to discrete structures
Forests and Trees (Vertex-to-edge relation in k-component acyclic graphs)
Planar Graphs, Face Bounds, and Euler's Formula
Handshaking Lemma and Minimum/Maximum Degree Relations
Chromatic Number (G) and Proper Vertex Coloring
Greedy Coloring Algorithm and Worst-Case Color Bounds
Independence Number (G) and Maximum Independent Sets
Hamiltonian Paths vs Hamiltonian Cycles
Graph Isomorphism and Girth/Degree Verification
Cayley's Tree Formula for Labeled Graphs
Connected components of an undirected graph
DFS spanning tree and spanning forest
Tree edge counting invariant (e = v - 1 per tree component)
Planar graphs and Euler's formula
Bounded vs unbounded faces in planar embeddings
Vertex colouring, chromatic number (G), and independent sets
Edge colouring, chromatic index '(G), and Vizing's theorem
Graphic degree sequences and Havel-Hakimi theorem
Bipartite graph recognition and 2-colorability
Self-complementary graphs and complement edge counts
Adjacency matrix powers (Ak)ij and trace properties for closed walks

Recurring question patterns

DAG Path Optimization with Custom Metric
occasional · NAT · 2 marks · 2021
A directed acyclic graph with edge weights is given, along with a custom path metric (e.g., product of edge weights) and an aggregation rule (e.g., maximum score from a source vertex). Candidates compute vertex-level scores via topological order relaxation and return an aggregate sum across all vertices.
Visual Graph Hamiltonicity / Traversal Feasibility
occasional · MCQ · 2 marks · 2026
Given one or more visual graph representations, determine whether a closed traversal visiting every vertex exactly once (Hamiltonian cycle) exists by checking structural properties like grid dimensions or forced subcycles from degree-2 vertices.
Fundamental Graph Invariants and Theorems
occasional · NAT · 1 marks · 2016
Direct retrieval or evaluation of fundamental bounds and theorems on graph classes, such as chromatic numbers or vertex-colouring requirements for planar graphs.
Adjacency Matrix Structural and Spectral Properties
occasional · MSQ · 2 marks · 2022
Multi-statement verification testing properties of graph adjacency matrices, powers of adjacency matrices (number of walks), vertex degrees, edge sums, and connectivity.
Extremal Overlap / Similarity Metric on Graph Subgraphs
rare · MCQ · 2 marks · 2026
Given a standard graph class (e.g., $K_n$ with $n > 4$ ) and a family of subgraphs (e.g., spanning trees), find the minimum or maximum value of a similarity metric (e.g., Jaccard coefficient) by determining if edge-disjoint configurations exist.
Structural Counting and Invariant Relationships
common · MCQ · 2 marks · 2014
Questions that evaluate edge, vertex, face, or component relationships using fundamental theorems like Euler's planar formula, Handshaking Lemma, or tree/forest decomposition formulas.
Special/Named Graph Property Verification
occasional · MSQ · 2 marks · 2022
Multi-statement verification (typically MSQ) assessing several graph parameters—such as chromatic number, Hamiltonian paths/cycles, graph isomorphism, and independence number—on well-known graphs (e.g., Petersen graph, complete bipartite graphs).
Graph Coloring and Greedy Bounds
occasional · MSQ · 2 marks · 2023
Analyzing bounds and correctness of vertex coloring procedures, comparing maximum degree $\Delta(G)$ , chromatic number $\chi(G)$ , and upper bounds from greedy algorithms.
Spanning Tree Enumeration
common · NAT · 1 marks · 2024
Direct numerical calculation of the number of spanning trees in labeled graphs using Cayley's formula or standard reduction rules.
DFS / BFS Spanning Forest Edge-Component Relation
rare · NAT · 2 marks · 2024
Given the total number of vertices $n$ in an undirected graph and the total number of edges in its traversal spanning forest (or tree edges), find the number of connected components $k$ using the invariant $E_F = n - k$ .
Planar Graph Invariants via Euler's Formula
common · NAT · 1.5 marks · 2021, 2015, 2012
Given vertices, edges, face-degree restrictions, or bounded/unbounded face distinctions, compute an unknown parameter using Euler's formula and face-edge handshaking.
Graph Colouring and Chromatic Bounds
common · mixed · 2 marks · 2024, 2020
Determine the vertex chromatic number $\chi(G)$ or edge chromatic index $\chi^{\prime}(G)$ of a given graph, or identify universal theoretical inequalities involving color classes and independent sets.
Degree Sequences and Handshaking Sums
occasional · mixed · 2 marks · 2014
Test whether a sequence of non-negative integers is graphic using Havel-Hakimi or degree counts, or calculate the total number of edges in a structured coordinate/grid graph.
Isomorphism and Complementary Graphs
occasional · NAT · 2 marks · 2014
Find parameter values (such as vertex count $n$ ) where a graph class is self-complementary or isomorphic to a derived graph.
Algebraic Graph Properties & Walk Counting
rare · MCQ · 2 marks · 2022
Relate powers and trace of the adjacency matrix $A^k$ to paths, closed walks, and small subgraph counts (such as triangles/3-cycles).

Formulas GATE uses

Max-Product Path Recurrence on DAG

Q(v) = \max_{(u, v) \in E} \{ Q(u) \times w(u, v) \}

Used to compute optimal path quality-scores for each vertex in a DAG starting from a base case $Q(\mathbf{s}) = 1$ .

Hamiltonicity of Grid Graphs

P_m \times P_n \text{ is Hamiltonian} \iff m, n \ge 2 \text{ and } m \cdot n \equiv 0 \pmod 2

Determining if a rectangular 2D mesh/grid graph contains a Hamiltonian cycle.

Degree Constraint in a Hamiltonian Cycle

\deg_{H}(v) = 2 \quad \forall v \in V(G)

Checking forced edge inclusion when a vertex has degree 2 in $G$ , which can lead to premature subcycles.

Four Colour Theorem

\chi(G) \le 4$ for any planar graph $G

Used to find the upper bound on the minimum number of colours required to vertex-colour any arbitrary planar graph.

Diagonal Entries of Adjacency Matrix Square

(A^2)_{ii} = \sum_{k=1}^n A_{ik}^2 = \sum_{k=1}^n A_{ik} = \text{deg}(v_i)

Used to determine that the diagonal entries of $A^2$ in a simple undirected graph represent the degrees of the vertices (number of closed walks of length 2).

Sum of Elements of Adjacency Matrix (Handshaking Lemma)

\sum_{i=1}^n \sum_{j=1}^n A_{ij} = \sum_{i=1}^n \text{deg}(v_i) = 2|E|

Used to relate the total sum of matrix entries to total edge count and evaluate acyclicity conditions.

Jaccard Coefficient for Edge Sets

J(T_1, T_2) = \frac{|T_1 \cap T_2|}{|T_1 \cup T_2|}

Used to compute the similarity ratio between the edge sets of two subgraphs.

Edge Bound for $k$ Edge-Disjoint Spanning Trees in $K_n$

k(n - 1) \le \frac{n(n - 1)}{2} \implies n \ge 2k

Used to establish the condition on $n$ under which two ( $k=2, n \ge 4$ ) or more edge-disjoint spanning trees can be packed into a complete graph.

Forest Edge Formula

|E| = n - k

Used to compute the total number of edges in a forest with $n$ vertices partitioned into $k$ connected components.

Handshaking Lemma

\sum_{v \in V} \deg(v) = 2|E| \ge n \cdot \delta(G)

Used to relate sum of vertex degrees, minimum degree $\delta$ , and edge count.

Euler's Formula for Planar Graphs

n - m + f = 1 + k

Used to relate vertices ( $n$ ), edges ( $m$ ), and faces ( $f$ ) for a planar graph with $k$ connected components (reduces to $n - m + f = 2$ for connected planar graphs).

Greedy Coloring Degree Upper Bound

\chi(G) \le \Delta(G) + 1

Used to bound the number of colors assigned by the standard sequential greedy coloring algorithm.

Cayley's Formula for Spanning Trees

\tau(K_n) = n^{n-2}

Used to calculate the number of spanning trees in a labeled complete graph $K_n$ on $n$ vertices.

Number of Edges in a Spanning Forest

E_F = n - k

Used to find the number of connected components $k$ , number of vertices $n$ , or total tree edges $E_F$ in a DFS/BFS spanning forest of an undirected graph.

Edges in a Tree Component

e_i = n_i - 1

Used when analyzing individual connected components of a spanning forest where each component $i$ has $n_i$ vertices.

Face-Edge Handshaking Relation

\sum_{i=1}^{F} \text{deg}(F_i) = 2E

Used when each face is bounded by a fixed or minimal number of boundary edges (e.g., $3F \le 2E$ for maximal planar graphs).

Complement Graph Edge Count

|E(\overline{G})| = \frac{n(n-1)}{2} - |E(G)|

Used when evaluating self-complementary graphs or complements of standard graphs like cycles $C_n$ .

3-Cycle Counting via Adjacency Matrix

\text{Number of 3-cycles} = \frac{\text{trace}(A^3)}{6}

Used to count triangles in a simple undirected graph from its unweighted adjacency matrix $A$ .

Vizing's Theorem (Edge Colouring)

\Delta(G) \le \chi^{\prime}(G) \le \Delta(G) + 1

Used to bound and determine the chromatic index (minimum edge colours) based on the graph's maximum degree $\Delta(G)$ .

Independence Number Lower Bound from Chromatic Number

\alpha(G) \ge \left\lceil \frac{n}{\chi(G)} \right\rceil

Used in theoretical bounds relating graph order $n$ , chromatic number $k$ , and maximum independent set size $\alpha(G)$ .

Examiner traps in Graph Theory

Forgetting to include the source vertex s in the final summation
Evaluating vertices out of topological order, leading to incorrect maximal values when multiple paths merge
Adding edge weights instead of multiplying them according to the defined path metric rule
Arithmetic errors when computing intermediate products with large weight multipliers
Confusing the Hamiltonian cycle requirement (visiting every vertex exactly once) with Eulerian circuit (visiting every edge exactly once).
Assuming a graph is Hamiltonian merely because it is 2-connected, ignoring forced smaller cycles created by multiple degree-2 vertices sharing identical neighbor sets.
Forgetting that an odd number of vertices in a bipartite or grid graph prohibits a Hamiltonian cycle.
Assuming |E| n - 1 guarantees acyclicity without confirming connectivity (e.g., disjoint union of C3 and an isolated vertex has |E| = 3 4 - 1 but contains a cycle).
Assuming minimum degree 1 (at least one non-zero entry in each row/column) implies graph connectivity (e.g., K2 K2 is disconnected).
Assuming odd/even walk parity reachability ensures all entries in An-1 + In are non-zero for connected bipartite graphs.
Confusing the general upper bound of planar vertex colouring (4) with specific planar sub-classes like triangle-free (3) or bipartite planar (2).
Confusing vertex overlap with edge overlap (spanning trees always share all n vertices, but their edge sets can be completely disjoint).
Assuming two spanning trees must share at least one edge even when n 4.
Ignoring constraints on n (e.g., n > 4) which guarantee the existence of edge-disjoint spanning trees.
Confusing Hamiltonian Path (visiting all vertices without closing) with Hamiltonian Cycle (closed tour), especially on the Petersen graph.
Assuming the greedy coloring algorithm always uses exactly the minimum number of colors (G) (greedy coloring is order-dependent and can require up to + 1).
Off-by-one errors when applying Euler's formula n - m + f = 1 + k versus n - m + f = 2 on disconnected or multi-component graphs.
Forgetting that Cayley's formula nn-2 applies strictly to labeled trees, not unlabeled isomorphism classes.
Assuming maximum independent set size (G) equals n/2 or 3 on Petersen graph instead of the correct value 4.
Confusing the number of edges in the original graph G with the number of edges in the DFS spanning forest EF.
Off-by-one errors by assuming the graph is fully connected (EF = n - 1) instead of accounting for multiple disjoint components (EF = n - k).
Incorrectly adding k instead of subtracting k in EF = n - k, leading to n + EF or other arithmetic missteps.
Confusing total faces F with bounded interior faces (Fbounded = F - 1).
Assuming (G) = k implies the presence of a complete subgraph Kk (cliques imply high chromatic number, but high chromatic number does not imply a clique, e.g., C5).
Forgetting that each 3-cycle is counted 6 times in trace(A3) due to 3 starting vertices and 2 traversal directions.
Neglecting isolated vertices (di = 0) during manual graphic sequence reductions.
Assuming every graph with (G) = k must have a vertex with degree k, rather than degree k - 1.

How questions are asked

Visual DAG diagram computation (NAT)
Visual graph property check (identifying Hamiltonian cycles across multiple diagrams)
Word problem mapping to graph traversal definitions
Fill-in-the-blank numerical evaluation for graph invariant bounds
Multi-statement evaluation of graph algebraic and topological properties
Extremal value optimization on subgraph edge sets
Direct closed-form formula selection
Inequality derivation combining Handshaking Lemma and Euler's formula
Multi-statement verification of graph invariants on standard named graphs
Algorithm correctness and bound analysis for graph coloring
Direct integer computation via counting formula (NAT)
Numerical calculation of graph components given vertex count and spanning forest edge count (NAT)
Planar face / edge arithmetic (Euler's formula computation)
Graphic degree sequence validation (Havel-Hakimi test)
Grid / coordinate graph edge counting via Handshaking Lemma
Graph chromatic index / number determination for custom constructed graphs
Theoretical multi-statement verification on graph coloring properties (MSQ)
Matrix representation property evaluation (walks and cycle counts via powers of A)

Paper trends

Introduction of custom algebraic path metrics (multiplicative path score rather than standard additive shortest/longest path) tested via 2-mark NAT visual diagram questions.
2021
Graph traversal concepts are contextualized as real-world routing/salesperson scenarios requiring direct visual inspection of small-to-moderate sized graphs.
2026
Shifted from a direct single-value theoretical recall question (1-mark NAT on chromatic bounds) to a rigorous multi-select question (2-mark MSQ) probing structural matrix properties and counterexamples.
2022, 2016
Introduction of interdisciplinary set-similarity definitions (e.g., Jaccard coefficient) applied to graph edge sets and spanning tree properties.
2026
Shift from single-correct structural derivation MCQs to multi-select questions (MSQs) requiring comprehensive analysis across multiple independent graph properties simultaneously.
2023, 2022, 2014
Inclusion of algorithmic discrete math questions (e.g., analyzing greedy vertex coloring behavior and performance guarantees).
2023
Direct evaluation of labeled tree counting using exact closed formulas appearing in low-mark NAT format.
2024
Recent papers use NAT format for graph structural properties combined with traversal concepts (DFS spanning forest), requiring candidates to apply component-tree counting without needing explicit graph visualization.
2024
Shift from standard 1-mark Euler formula MCQs toward 2-mark NATs and theoretical MSQs probing deeper structural properties of chromatic numbers and independent sets.
2024, 2021, 2015, 2012
Introduction of algebraic graph theory concepts (trace of adjacency matrix powers for cycle counting) alongside traditional combinatorial graph theory.
2022
Continued reliance on NAT format for numerical structural graph parameters (edge counts, chromatic numbers, vertices in self-complementary graphs).
2024, 2021, 2020, 2015, 2014

Difficulty notes

Medium difficulty is driven by the number of vertices (requiring careful step-by-step dynamic programming along multiple branching and merging paths) and the need to sum over all 9 vertices without calculation errors.