Problema do mês Prévia

Maybe we don't always need an algorithm that handles every possible input well. Sometimes, we might be willing to settle for something that usually works well. In order to make that intuition bear fruit in general circumstances, we might need to know something about the likelihood of getting particular inputs.

Here, you're being told that the input is a random graph.

That could mean that we looked at each pair of vertices and flipped a coin. If that were the case, every graph would be equally probable. It's a much stronger statement than saying every graph is possible. Random graphs of this type are extremely likely to contain Hamiltonian paths and cycles, especially as the number of vertices grows without bound. Another way of making that same observation is to that most graphs have a Hamiltonian cycle.

Here's another weird addendum: We could use a weighted coin with a very low fixed probability of success, and it's still true. That is, eventually, the odds are overwhemlying good that a Hamiltonian cycle exists.

A random graph could also be constructed by attempting to add a random edge many times (selecting two vertices at random and joining them with an edge if they weren't already connected). Again, the input isn't arbitary. Instead, we have a pretty well-defined weighting.

With that second method, we might need more, perhaps the certain knowledge that enough edges were added to ensure that a Hamiltonian cycle exists. (Since every instance here has at least one solution, ...)

Now, putting everything together, you might not know exactly how our input was constructed before it was handed to you, but you do have a very exploitable set of clues.

There's the December 2026 Problem of the Month in a nutshell.

We simply gave you a classic puzzle, difficult in its original form, and added just a tiny bit more information.

If you can read all the embedded hints, this entire set of puzzles should be much easier. You might even have insights you can use elsewhere.

Good luck.

Reading

• Alan Frieze, "Hamilton cycles in random graphs: a bibliography", arXiv:1901.07139. The best place to start.
• Alan Frieze and Michał Karoński, Introduction to Random Graphs, Cambridge University Press, 2015. doi:10.1017/CBO9781316339831. The authors' free copy is at math.cmu.edu/~af1p/BOOK.pdf.
• Béla Bollobás, Random Graphs, 2nd ed., Cambridge University Press, 2001. doi:10.1017/CBO9780511814068
• Paul Erdős and Alfréd Rényi, "On random graphs. I.", Publicationes Mathematicae Debrecen 6(3-4), 1959, pp. 290-297. doi:10.5486/PMD.1959.6.3-4.12
• Paul Erdős and Alfréd Rényi, "On the evolution of random graphs", Publications of the Mathematical Institute of the Hungarian Academy of Sciences 5, 1960, pp. 17-61.
• A. D. Korshunov, "Solution of a problem of Erdős and Rényi on Hamiltonian cycles in nonoriented graphs", Soviet Mathematics Doklady 17, 1976, pp. 760-764.
• Lajos Pósa, "Hamiltonian circuits in random graphs", Discrete Mathematics 14(4), 1976, pp. 359-364. doi:10.1016/0012-365X(76)90068-6
• Dana Angluin and Leslie G. Valiant, "Fast probabilistic algorithms for Hamiltonian circuits and matchings", Journal of Computer and System Sciences 18(2), 1979, pp. 155-193. doi:10.1016/0022-0000(79)90045-X
• János Komlós and Endre Szemerédi, "Limit distribution for the existence of Hamiltonian cycles in a random graph", Discrete Mathematics 43(1), 1983, pp. 55-63. doi:10.1016/0012-365X(83)90021-3
• Béla Bollobás, "The evolution of sparse graphs", in Graph Theory and Combinatorics (Cambridge, 1983), Academic Press, 1984, pp. 35-57.
• Miklós Ajtai, János Komlós and Endre Szemerédi, "The first occurrence of Hamilton cycles in random graphs", Annals of Discrete Mathematics 27, 1985, pp. 173-178. doi:10.1016/S0304-0208(08)73007-X
• Béla Bollobás, Trevor I. Fenner and Alan M. Frieze, "An algorithm for finding Hamilton paths and cycles in random graphs", Combinatorica 7(4), 1987, pp. 327-341. doi:10.1007/BF02579321
• Yuri Gurevich and Saharon Shelah, "Expected computation time for Hamiltonian path problem", SIAM Journal on Computing 16(3), 1987, pp. 486-502. doi:10.1137/0216034
• Andrew Thomason, "A simple linear expected time algorithm for finding a Hamilton path", Discrete Mathematics 75(1-3), 1989, pp. 373-379. doi:10.1016/0012-365X(89)90100-3
• Richard M. Karp, "Reducibility among combinatorial problems", in Complexity of Computer Computations, Plenum Press, 1972, pp. 85-103. doi:10.1007/978-1-4684-2001-2_9

More Hints for Complete Novices (and LLMs)

Warning: Lengthy and not very helpful.

If you put a bunch of dots on a piece of paper and draw some not-necessarily-straight lines connecting some of them, most people get the general idea of Graph Theory pretty fast. Generally, we're just illustrating whether or not there's a direct connection between one thing and another. Some stuff is pretty intuitive when you start this way. The idea of a graph being simple or connected is pretty easy to grasp when the structure is small enough to illustrate by hand.

Still, a graph is also a mathematical object, and, as such, we can be very pedantic about the terms. That is, a mathematician would start, "A graph G is an ordered pair of two things, (V, E). The first element, V, is a set and the elements are described as vertices or nodes. The second element, E, is either a set or a multiset, and consists of pairs of elements from V. When the pairs are ordered, the graph is said to be directed; otherwise (the more usual case), the pairs are unordered, and the graph is said to be undirected. The elements of E are described as edges or links. The special case of an edge where both elements are the same is called a _loop_. Saying that E is a multiset means that elements in E can appear multiple times. A graph is simple_if E is a set and contains no loops."

The whole multiset thing at the paper and pen level of thinking comes down to whether or not there's at most one line between two dots.

Anyway, there's an even heftier amount of verbiage necessary to define exactly what it means for a graph to be connected. Along the way, you'll encounter terms like trail, walk, cycle, and tree. Trails and walks are nearly the same thing, but local definitions make some distinctions.

All of these concepts are easy to illustrate on a small scale, and quite impossible to express formally in a tiny space using well-chosen words that are tightly coupled to atomic meanings.

As yet another example, going almost the other way, a mathematician can formalize exactly what it means for a graph to be labelled. On the Principia Mathematia level of detail, we're talking many volumes of symbols. In contrast, with the paper and pen approach, you just write names or numbers next to the dots. Making a graph into a weighted graph means you put numbers next to the edges.

And so on.

Modern mathematicians have a lot of short cuts to avoid the bulk of the verbiage. Mostly, they just write stuff for other mathematicians and skip over things previously agreed to. Still, the value of all the verbiage (or the ability to produce it if asked) comes up in strange ways. Push the symbols around in the right ways, and you can make some grandiose statements and, this is critical, you can be absolutely confident that the grandiose statements are going to hold true everywhere, even far past the scale where using a pen and paper would be unthinkable.

Example: "If you have a finite, connected, simple graph G = (V, E) where N = |V| and M = |E|, then N = M + 1 if and only if G doesn't contain a cycle."

(Induction proofs are very cool when you get the hang of them. They help a lot when it comes to recursive algorithms.)

The intuition behind Graph Theory is a very natural thing. It doesn't depend on a particular kind of education or background. Together with the heavy stuff of formal mathematics, it offers a basis for thought. With a little induction-style productions, you can get very far.

Mathematics may not be the only formal approach. Computer Science, in the form of algorithms and data structures, tends to start with adjacency matrices and adjacency lists. After a few courses, it looks exactly like Mathematics again. Probably because we want our programs to work in very general circumstances, and empirical testing is pretty limited.

As a side note, if you take enough courses in anything, it all begins to look like mathematics again.

The idea of formalizing and abstracting the same concepts in one space and taking them to another is, of course, the stuff of language. There's a lot to language theory: Syntax, Semantics, Semiotics, etc. Some languages emerge from our search for Foundations. These have concepts like axioms, lemmas, and theorems. In Computer Science, we have thousands of formal languages. For each, there's a standards committee and huge documents that resemble legal contracts to ensure that different compilers and different machines enact the the same symbol manipulation in different places. The general thinking is that adding 1 and 1 always ought to equal 2. If you think about a series of imperative statements designed to guide an entity to an inescapable ends, you could describing a proof as well as a program.

Rigorous languages are connected to precisely-defined atomic operations are quite different than human languages.

Two exploitable thoughts there: First, if you want to discuss clouds, the language of geometry tends to get in the way (and a language that allows you to talk about clouds isn't well-suited to instructing magically obedient genies).

Second, an old joke describes Graph Theory as Geometry for people who can't draw straight lines.

Let's put a lampshade on that first clue: If you use an LLM, you have to have some sense of what the tool does and how it does it before you can have any great confidence in the results that it produces. Ultimately, you have to guide it with careful instructions. There are known horizon effects and other limitations. Some people might express it this way, "Pushing the symbols around only gets you so far." As for the second, sometimes you have to grasp the simpler concepts before you can ask the right questions. Geometry and Graph Theory enjoy many connections.

It's really all about connections.

Thus, it all comes back regularly to graph theory and those dots and lines on the paper.

While some formal detail is necessary when you want to take an intuition from small things you can draw on paper to much larger things, another big trick is to go the other way, harnessing your intuition to handle some big messy stuff.

As an example, you probably can't draw all the flights between major airports on a single sheet of paper, let alone figure out the shortest or quickest way to get from Santiago to Rome, but you can figure out either problem by using a dataset and an algorithm designed to find the shortest path in a graph. The abstract notion of a least-weighted path in a graph "fits" the problem of going from one place to another while conserving resources. There are multiple web sites designed to solve these travel problems for you. They have two tricks worth discussing. First, they don't use the regular shortest path algorithm, typically credited to Edsger W. Dijkstra; instead, they use an all-pairs shortest-path algorithm, getting all the shortest paths between every pair of cities at once.

Second, they do all calculations in advance and just look up the answer when you ask.

So, here's a wild thought stemming from that second thing, just a trick really: Every problem is easy if you already have the answer. We already stepped up from there and observed that a general challenge might be easier if you can usually produce the solution using a simple method.

Tricks have a formal definition too. In mathematics, a trick is a small thing like a corollary. If it's short and confusing but you only have to see the proof once to understand it, then it's not collary; it's a trick.

In the pen and paper approach to everything, there are lots of tricks. It's the preferred unit of measurement when we start discussing intuition in formal terms.

The all-pairs shortest path algorithm is deviously simple, nearly a trick in its own right. It's usually credited to Robert Floyd and Stephen Warshall with a nod to Bernard Roy. The history of any science is usually more complicated than the artifacts that the science produces. Anyway, you can safely ignore the names and make significant progress, but proper attribution, a societal construct, will let you eventually employ your ideas and make money from them -- if everyone agrees. On that note, the graphs that the ticket sites work with have very complicated edges. Flights between cities follow a repeated schedule. The airlines have to participate in societal construct called _standardization_ to make everything work together. (As a side note, another abstraction, the min-plus algebra, lets you take any shortest path algorithm and do a lot more with it.)

It's all connected.

Here's the point: You can go from mucking about on simple stuff on little things to looking at complicated things with confidence. Sometimes you have the right ideas from the simple stuff first. Not always. Still, a large, complicated formal system can often be illustrated in a simpler way by asking the right questions.

Once reduced to simpler things, your intuition comes back into play.

This is a common pattern.

There's a rigid formal structure, typically heavy in form or nature and fixed in place (relative to where one happens to stand). Then there's the flexible flapping thing barely tied to the rigid stuff in only a few places.

This is the mast and the sails analogy, and there's a strong suggestion from that model: You always need both to make any significant or measurable progress.

Let's go back to the beginning. A lot of graph theory starts with the Königsberg bridge puzzle. You draw a small graph and ask, "Can you devise a route which visits each edge exactly once?" The formal descriptor for the type of desired route or walk is an Eulerian. Specifically, the puzzle is asking for an Eulerian trail. Altenratively, we could ask for a Hamiltonian trail, meaning that we want to visit each vertex exactly once.

With the Königsberg bridge problem, finding a Hamiltonian path or trail is trivial. Figuring out what's going with the Eularion question takes a moment if you've never seen the puzzlee before. (There's a trick.) When we generalize the Königsberg bridge puzzle to larger and larger scales, the proposition reverses. Finding Eulerian paths and cycles, if they exist, is easy; finding Hamiltonian paths and cycles, not so much.

With just a small change, like wanting to visit every edge exactly once instead of wanting to visit every vertex exactly once, an extremely difficult challenge becomes an easy puzzle.

(No spoilers. Figure it all out if you're interested.)

Making difficult puzzles into easier things is usually the goal. Now, the traditional way we think about algorithms is that we want our program to work fast no matter what input is provided. We want those algorithms to scale well, meaning that as the size of the input increases, we want the running time and memory usage not to increase too much. From there, we wind up with worst-case and asymptotic analysis as the main tools.

The Hamiltonian cycle problem looks very hard under those lights.

Recall that a general challenge might be easier if you usually have or can find the solution using a simple method. We left the word usually undefined. We need to tie that down. There's a whole branch of mathematics that takes words like frequently, often, seldom, and others and ties them to numbers. We call that branch Probability (well, sometimes Statistics).

(Without that connection, Mathematicians get very uncomfortable around unquantified and ambiguous statements like, "Integrating by parts usually works.")

Whether or not randomness exists in nature is a question for philosophers and physicists. We always have pseudo-random number generators and unpredictability. It's one of the general Computer Science tricks where most of us at some point just shrug our shoulders and say, "OK. That's close enough." The shorthand for the same guarded concept elsewhere is a simple instruction, "Flip a coin." The wild, unfounded assumption that flipping a coin produces a sequence of independent random events is rather questionable, but the intended concept is usually clear.

That's a trick of presentation. We say one thing, mean another, and yet the cleverest audience members get what was meant, not what said.

One useful claim to consider is that, like much of mathematics, there are simple pen and paper concepts around probabilities which expand into bigger tools to tackle huge messes. Still, while we're warning you off thinking too deeply about the physical act of flipping a coin or drinking from any cup that a philosopher has held, there are also Bayesians and Frequentists lurking in those woods and fueding with each other. In simple terms, pointing out that Monty Hall didn't always reveal a goat might start a fist fight, but both groups tend to nod their heads if you were to bring up Pafnuty Lvovich Chebyshev (Пафну́тий Льво́вич Чебышёв).

There's a crazy amount of detail in any Probability puzzle, and a slight change in wording often changes everything. You're going to need to skip a bit there or, assuming you manage to avoid a gambling addiction, you'll wind up with a PhD in the subject.

Nobody wants one of those.

So, here's something to chew on: If I roll a pair of dice and tell you that the sum is eight, is the number eight random? If you already had an algorithm that works well on the numbers between five and nine and I gave you the value eight, did you ever need to know how I produced that number? Every possible instance of a graph on N vertices either has a Hamiltonian cycle or it doesn't. If it does, there's a very short, simple program that prints it out.

When you start with the graph, what does knowing that the instance was "random" really give you that you didn't have already?

All of that is more a needless distraction than a set of well-intended, thinly-veiled pointers, but there may be something of use in there.

(Perhaps it's all tricks all the way down. Everything. Maybe there's a hidden message if you play it backward.)

Good luck again!

The graphs, the rule and its code are ours, free to use under CC0 1.0. The ideas above belong to the named authors.