<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Udit Singh Bhadouria on Medium]]></title>
        <description><![CDATA[Stories by Udit Singh Bhadouria on Medium]]></description>
        <link>https://medium.com/@usb233?source=rss-169977ded049------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/0*-8YYBhLW3KYo9PXh</url>
            <title>Stories by Udit Singh Bhadouria on Medium</title>
            <link>https://medium.com/@usb233?source=rss-169977ded049------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Wed, 18 Nov 2026 21:55:45 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@usb233/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Hamiltonian Paths: Visiting Every Dot Exactly Once]]></title>
            <link>https://medium.com/@usb233/hamiltonian-path-in-graph-theory-a-concept-illustration-b2401290f5ad?source=rss-169977ded049------2</link>
            <guid isPermaLink="false">https://medium.com/p/b2401290f5ad</guid>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[graph-theory]]></category>
            <category><![CDATA[computer-science]]></category>
            <category><![CDATA[hamilton]]></category>
            <category><![CDATA[education]]></category>
            <dc:creator><![CDATA[Udit Singh Bhadouria]]></dc:creator>
            <pubDate>Sun, 04 Oct 2026 16:50:33 GMT</pubDate>
            <atom:updated>2026-10-05T15:42:17.362Z</atom:updated>
            <content:encoded><![CDATA[<p><em>A picture-first tour of graph theory’s most deceptive little problem.</em></p><h3>Introduction</h3><p>Plenty of problems in computer science announce themselves as trivial. This is one of the worst offenders: “join up all these dots with a single line, and don’t lift your pen.” That’s it. Yet this throwaway question — the Hamiltonian path problem — is buried under delivery routing, DNA sequencing, chip layout, and one of the most stubborn open questions in all of mathematics.</p><p>Here is the trick it plays. A child can grasp the goal in about five seconds. Then you add a handful of dots, and the machines we are proudest of start to wheeze. Nobody on the planet knows a method that stays quick on every graph. That chasm between “easy to say” and “brutal to do” is what this post is about, and I have leaned on diagrams throughout so that no background is needed.</p><h3>What a Hamiltonian path actually is</h3><p>Strip the notation away and a graph is just dots wired together by lines. The dots are called vertices; the lines are called edges. A Hamiltonian path is a walk that plants itself on every vertex exactly once. It may start and stop wherever it pleases, and it is under no obligation to touch every edge.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*F_A858EWjFpP8iNdGVwWzg.png" /><figcaption><em>Figure 1: The red route is a Hamiltonian path. It uses all seven vertices, each exactly once.</em></figcaption></figure><p>The name honours William Rowan Hamilton, an Irish mathematician who in 1857 tried to sell a puzzle called the Icosian Game. It revolved around a twelve-cornered shape, and the player’s task was to trace precisely this sort of route. The toy sank without a trace. The question behind it refused to die, and outlived the game by more than a century and a half.</p><h3>Putting it precisely</h3><p>It pays to pin the same idea down in exact language. Write a graph as G = (V, E), where V gathers the vertices and E gathers the edges. A Hamiltonian path is then a sequence of distinct vertices</p><p><em>v₁, v₂, …, vₖ</em></p><p>in which every neighbouring pair is joined by an edge and the sequence accounts for every vertex in the graph, so k = |V|. Demand one extra thing — that the final vertex also connects back to the first — and you have a Hamiltonian cycle: the route seals itself into a ring.</p><p>Notice everything the definition stays silent about. It never insists that each edge be used once. It never asks for the shortest route. It does not even require the graph to hang together in one piece. Covering every vertex is the sole demand, and that single-mindedness is exactly why the problem is so easy to state and so vicious to solve.</p><h3>Path vs. Cycle</h3><p>When a Hamiltonian path happens to wander back to where it began, you get a Hamiltonian cycle (some writers say circuit). Every vertex is still visited once, but now the route bites its own tail.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*4CN41RTsvki4Wx66xwTHuA.png" /><figcaption><em>Figure 2: The path bends back to vertex 0, closing the ring into a Hamiltonian cycle.</em></figcaption></figure><p>That distinction is not a technicality. A cycle is the heavier demand, and plenty of graphs cough up a path while stubbornly refusing a cycle — we will meet one soon. In practice it is the cycle we usually want, because a route that carries you home beats one that dumps you at the far end.</p><h3>The mix-up everyone makes: Euler versus Hamilton</h3><p>These two get confused constantly, so let us settle it with a single picture.</p><ul><li><strong>An Euler path</strong> uses every edge exactly once, and vertices are free to repeat.</li><li><strong>A Hamiltonian path</strong> visits every vertex exactly once, and edges are free to be skipped.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*j0naNL-4rg4JKiW4didgtg.png" /><figcaption><em>Figure 3: Two look-alike tasks with different targets. Count edges on the left, vertices on the right.</em></figcaption></figure><p>Here is the twist that turns the pair into a genuine lesson: Euler paths are easy, Hamiltonian paths are not. A single sweep settles whether an Euler path exists — it does precisely when the graph is connected and has zero or two odd-degree vertices. Hamiltonian paths enjoy no such mercy. No tidy rule, no quick pass, no shortcut test. Two problems that look like twins behave like total strangers, and that gap is your first honest taste of complexity theory.</p><h3>Worked example: finding one by hand</h3><p>Before reaching for a computer, do one by hand. The feel of the search matters more here than any code. Take the five-vertex graph below.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/960/1*jC0hfNeRhH3UzSAeFCBZhQ.png" /><figcaption><em>Figure 4: Five vertices, one valid Hamiltonian path picked out in red.</em></figcaption></figure><p>Start somewhere and grow the path one step at a time, always stepping onto a vertex you have not touched. From A, take B. At B the only fresh neighbour is D, so D it is. From D we move to C. And from C the last unvisited vertex, E, is right there. The result is A → B → D → C → E: five vertices, each used once.</p><p>Now watch how close this came to failing. Jump from A straight to C at the start, and you have painted yourself into a corner with vertices still stranded, forcing you to undo the move and try again. That retreat-and-retry dance is exactly what a computer does under the hood — and exactly what makes the cost detonate as the graph grows.</p><h3>How a computer hunts for one</h3><p>The straightforward approach is called backtracking. Extend the path one vertex at a time; the instant you are stuck, rewind and pick a different branch. It is trivial to write, and it always finds a path if one exists. The catch is the worst case: it may wade through roughly n! possibilities, a number that balloons far faster than intuition expects.</p><p>A cleverer option is Held–Karp. Rather than remembering whole routes, it remembers answers to smaller sub-problems. For each little group of vertices, it records the cheapest way to arrive at each one. This trims the work from about n! down to roughly O(n²·2ⁿ). A spectacular saving — and still hopeless once the graph holds more than a few dozen vertices.</p><p>Since exact answers cost so much, real software leans on heuristics, fast rules that return a good route without promising the best one. Nearest-neighbour always hops to the closest unvisited vertex. Then 2-opt polishes the tour by un-crossing pairs of edges. For the delivery version of the problem, an algorithm called Christofides even guarantees a route no worse than 1.5 times optimal — a rare and rather charming promise in a field this unforgiving.</p><h3>When is one guaranteed to exist?</h3><p>No fast exact test exists, but mathematicians have still managed to prove conditions under which a cycle must appear, based purely on how densely connected the graph is. Two of the most quoted:</p><ul><li><strong>Dirac’s theorem (1952):</strong> if a graph has n ≥ 3 vertices and every vertex has at least n/2 neighbours, a Hamiltonian cycle is guaranteed.</li><li><strong>Ore’s theorem (1960):</strong> if every pair of non-adjacent vertices u and v have degrees summing to at least n, a Hamiltonian cycle is guaranteed.</li></ul><p>Read these as guarantees, not fences. A graph can fail both tests and still turn out to be Hamiltonian. Ore’s result is really a strengthened Dirac’s, and together they show the way mathematicians nibble at a hard problem from its edges.</p><h3>The hard part</h3><p>This is why the topic carries such a reputation. Deciding whether a Hamiltonian cycle exists is NP-complete. It was one of the 21 problems Richard Karp proved hard in 1972. In everyday language: no one knows a method that stays fast on every graph, and finding one would hand you a million-dollar prize.</p><p>Why so brutal? Brute force means testing every possible ordering of the vertices, about n! of them. At a mere 20 vertices that is more than 2.4 quintillion orderings to sift through. And to see that well connected does not mean Hamiltonian, meet the Petersen graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/992/1*zt0iTK-GuGP7kMgG1SYt6w.png" /><figcaption><em>Figure 5: The Petersen graph carries a Hamiltonian path (in red) but, famously, no Hamiltonian cycle.</em></figcaption></figure><p>It is flawlessly symmetric, and every vertex has exactly three neighbours, yet no cycle can thread through all ten vertices once. Cases like this are why gut instinct is worthless here, and why the problem deserves its fearsome name.</p><h3>Families of graphs that behave</h3><p>Some families of graphs are always Hamiltonian, and knowing them sharpens your intuition.</p><p><strong>Complete graphs.</strong> When every vertex connects to every other vertex, written Kₙ, you can tour the vertices in any order you please, so a Hamiltonian cycle is always there.</p><p><strong>Grids and meshes.</strong> Rectangular grids, the ones we use to model circuit boards and pixel arrays, are Hamiltonian too. That is exactly why a routing tool can snake through them in a single clean pass.</p><p><strong>Bipartite graphs.</strong> Here a plain counting rule draws blood. If the vertices split into two groups with edges running only between the groups, a Hamiltonian cycle can exist only when both groups are the same size. Picture a chessboard: every move flips the colour, so black and white squares must come in equal numbers.</p><p><strong>The knight’s tour.</strong> This one is the classic puzzle in disguise. Turn each of the 64 squares into a vertex, and join two squares whenever a knight can jump between them. A full knight’s tour, every square visited once, is nothing more than a Hamiltonian path on that graph.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/992/1*XdJH9XN1THCq39SStb3SyQ.png" /><figcaption><em>Figure 6: A complete knight’s tour on the 8 by 8 board, which is really a Hamiltonian path hiding inside the knight-move graph.</em></figcaption></figure><p>A delightful example, because a puzzle that looks like a game turns out to be the same hard problem wearing a costume.</p><h3>Where it turns up in the real world</h3><p>The Hamiltonian cycle is quietly buried inside a surprising number of everyday tasks.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*IGdMW_737FeEn7PdTUGVgw.png" /><figcaption><em>Figure 7: The Travelling Salesman Problem is the hunt for the shortest Hamiltonian cycle across a set of cities.</em></figcaption></figure><ul><li><strong>Delivery and routing.</strong> The Travelling Salesman Problem is literally the search for the cheapest Hamiltonian cycle. Van fleets, couriers, and delivery apps all live on good approximations of it.</li><li><strong>Reading DNA.</strong> Reassembling a genome from short fragments becomes a path problem over an overlap graph.</li><li><strong>Chip design.</strong> Routing wires so every component is reached without wasted length.</li><li><strong>Scheduling and factories.</strong> Ordering jobs, or drilling holes across a board, so a machine hits each point exactly once.</li><li><strong>Games and puzzles.</strong> The knight’s tour above, and Hamilton’s own Icosian Game.</li></ul><p>Every one of these hides the same shape: a set of places that must all be visited, and the search for a single clean pass through them.</p><h3>Why it makes a great teaching topic</h3><p>As a teaching example, the Hamiltonian path is unusually kind:</p><ol><li><strong>Nothing to learn first.</strong> Anyone can draw dots and lines, so nobody is locked out at the start.</li><li><strong>A sharp contrast.</strong> Sit it beside the Euler path and you learn that near-identical problems can differ wildly in difficulty. That is a first glimpse of complexity theory.</li><li><strong>A puzzle you can hold.</strong> Students can hunt for a path by hand, get stuck, and feel the options multiply instead of merely being told they do.</li><li><strong>A doorway to deep ideas.</strong> It opens naturally onto NP-completeness, approximation, and heuristics like nearest-neighbour and 2-opt.</li><li><strong>You can see the answer.</strong> Every claim can be drawn, checked, and disproved with a picture, which is the whole joy of graph theory.</li></ol><p>Try this in class: hand out the Petersen graph and ask for a Hamiltonian cycle. Nobody will find one, and that failure is the lesson.</p><h3>A little history</h3><p>The roots run deeper than most textbooks let on. Hamilton’s Icosian Game of 1857 is the popular starting point, but in that very year Thomas Kirkman was already publishing related puzzles with shapes, and later Peter Guthrie Tait explored how the problem tied into map colouring. For decades it was treated as harmless amusement. It only became a serious computer-science topic in 1972, when Karp showed it belonged to the NP-complete family, meaning a fast solution here would instantly unlock fast solutions to thousands of other hard problems. That is why a Victorian parlour game still matters to anyone who writes software today.</p><h3>Conclusion</h3><p>The Hamiltonian path is a small idea with an unusually long shadow. It is easy to describe, easy to sketch, and just as easy to get wrong. It threads a puzzle from the 1800s through modern computing and into the delivery app on your phone, and it teaches algorithm design its sharpest lesson: something can look simple and still be anything but.</p><p>So next time you map out a route through a handful of stops, remember that you are solving a Hamiltonian problem — and, in all likelihood, only approximating the answer.</p><h3>References</h3><ol><li>Dirac, G. A. (1952). Some theorems on abstract graphs. Proc. London Math. Soc.</li><li>Ore, O. (1960). Note on Hamilton circuits. Amer. Math. Monthly.</li><li>Karp, R. M. (1972). Reducibility among combinatorial problems.</li><li>Cormen, Leiserson, Rivest &amp; Stein: Introduction to Algorithms, Ch. 34 (NP-completeness).</li><li>Rosen, K. H., Discrete Mathematics and Its Applications, Graph Theory chapter.</li></ol><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b2401290f5ad" width="1" height="1" alt="">]]></content:encoded>
        </item>
    </channel>
</rss>