Start Doing Graph Theory | Hacker News Reader

Start Doing Graph Theory

vertex.degree

599 pointsibobev131 comments

I’ve been using graph theory for years professionally. A good example of practical uses of graph theory is any routing software. It is basically graphs all the way down.

For starters the whole street network is represented as a directed graph. The most widely used algorithm is the venerable A* to find paths through the vertices of the graph, not necessarily the shortest distance but the most optimal distance given all the trade-offs you wish based on the heuristics you define. There are lots of variations of A* and today most implementations would use its faster cousin: bidirectional A* which attacks the point-to-point calculation from both ends at the same time.

Then you have Dijkstra which is used for flood searches to e.g. give the best cost back home from every vertex so you know when to turn back the search if you have a search budget.

Menger’s theorem I’ve used in order to determine whether we can create a loop back. Basically search outwards, then search back without visiting those same edges.

Tarjan to ensure we identify all subnetworks so we don’t get stuck in a disconnected island of vertices with no way out to join the wider network.

A lot of these algorithms were conceived decades ago and are still the backbone of modern routing software.

One thing that’s constantly been in the back of my mind is, since routing is a highly deterministic problem space, it doesn't seem plausible that LLMs can take this over. It seems to me that it's a good example of a tool that LLMs would call out to rather than implement themselves.

In fact, see this convo I had with @simonw wherein he had Astra generate a jogging route. It setup a whole GIS stack and took about half an hour. That seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal. https://x.com/baz_shkara/status/2099118620647305630

> seems like a boil the ocean kind of approach and I’m not sure if that’s ever going to be optimal

Finding the most optimal traveling salesman problem for 20 cities by brute force will take a few universes lifetimes and you still won’t be halls way. You’ll need to compromise with heuristics but that usually leads to near optimal

It depends on what you mean by brute force, you can easily do 20 cities with dynamic programming, which essentially is brute force with pruning.

:faceslap:

I was always under the impression that by pruning you could only find the lowest bound on a branch but it wouldn't lead to the optimal path. TIL!

Although the simplest exact algorithm for TSP is O(n!), you can use dynamic programming to get the difficulty down to O(n^2 * 2^n), which is quite tractable at n=20.

However, sometimes you can construct exact solutions to much larger real-world data sets (tens of thousands of points) by exploiting structure in those graphs.

See my other comment. I feel stupid now

I've been doing a lot with graphs over the past couple of years. Basically since I started using neo4j, although not everything involves neo4j directly. I've developed a number of really interesting graph algorithms, but I'm always a bit disappointed by how little use I get out of my graph theory knowledge. I've never needed a Hamilton path or do something with the degrees of my vertices. It's all just logic and intuition.

But maybe I should read this to see if there's anything that applies to my current work.

My personal experience has been that the simpler undergrad algorithms are the most applicable. That’s probably also why you learn them first.

IMO, it’s much more practical to thoroughly learn and understand the simpler techniques. There is often more depth to it, than you’d think.

Analogy: Many (most?) MMA matches are won with techniques you learn in the first year.

Aside: I’ve gotten much more mileage out of simple statistics in the 16 years since I graduated, than advanced algorithms.

EDIT:

IMO, theories and techniques can be easy enough to learn. Figuring out applications can be much more difficult. It requires some creativity.

One very very useful but underused[1] application of graph theory (and its application of network theory): parts data systems' configuration management.

In a hardware manufacturing setting, particularly a new or "garage" sort of shop doing lots of new business, you quickly get into a nightmare scenario of "Too Many Configurations" running headfirst into the problem of "People Are Buying Too Much of Our Stuff". As a garage shop you can do OK making five or six units of all kinds, but once the orders for 1000, 10000 start coming in, you will be torpedoed by the complexity of keeping all those lines operational. Eventually you'll screw something up, and get dinged or even blacklisted (a big deal in Defense).

But it's a problem that can be steered around by applying some graph theory to the parts data system. Some PDMs actually do this natively - Oleg Shilovitsky's OpenBOM; Yoann Maingon's Ganister, both smart guys buy their stuff! - but this network theory can be used as a reporting layer on top of any big dumb PDM.

Examples include:

(Asciidoc table from a previous slide I've used, sorry)

    |===
    | Method | Primary Use
    
    | In-degree centrality | Shared/high-risk components
    | Out-degree centrality | Complex assemblies
    | Betweenness centrality | Change risk
    | Closeness centrality | Architectural centrality
    | PageRank | Strategic component
    | Degree distribution | Architecture health / power law check
    | Connected components | Find orphans
    | Shortest path / diameter | BOM depth, lineage distance
    | Clustering coefficient | Modularity vs. coupling
    | Community detection | Platform map, family boundaries
    | Ego network | "Minimum Safe Distance" of a change impact
    | Jaccard similarity | Variant/redundancy
    | Structural holes | "Bridge" component(s)
    | Topological sort | Flat assembly sequence
    | Longest path | Maximum BOM depth
    | Transitive closure | Full ancestor/descendant sets
    | Treewidth | Overall architectural complexity score
    |===

[1] Not counting Design Structure Matrix (DSM) / Multiple-Domain Matrix (MDM), which are kissing cousins to this sort of approach. See also Steven Eppinger (MIT) and Tyson Browning Design Structure Matrix Methods and Applications

Graphs are fantastic - PageRank [1] that powered Google Search (still does to some extent), TextRank for extractive text summarisation [2], Louvain for neighbourhood detection [3] all use graphs, as well as tonnes of others like belief propagation, Markov clustering, A*, and so on. So yeah, learn it.

[1] https://en.wikipedia.org/wiki/PageRank

[2] https://aclanthology.org/W04-3252.pdf

[3] https://en.wikipedia.org/wiki/Louvain_method

A problem I didn’t even conceive of a year ago was whether or not a book was written by a human.

This author has done nothing to deserve that scrutiny, but I can’t escape the feeling now of having to be guarded when I see a new book online with a relatively short history (spring 2026 is the earliest version of this text), as I can’t be sure it’s either “AI-enhanced” or AI-written.

I don’t like this feeling and it dampers any enthusiasm I once had for being excited about stuff like this.

That aside, if the author did write this themselves without AI, kudos to them and their acheivement!

I spot-checked a few random chapters, and it looks clearly human-written to me. But I share your general worry.

This is what we are supposed to have book and movie reviewers for. Just to check for slop regardless if the slop is AI or human.

But who reviews the reviewers?

What is the problem if it is AI written? Properly guided AI writes better than most human expositors.

Because it will absolutely have hidden errors.

Thank goodness human books never have hidden errors.

There are a few issues if it’s AI-written/edited/drafted:

1. AI generated text works off of whatever model it came from, whatever prompt was used, and probabilities. It’s been described as a “next token predictor” and that, for the purposes of this answer, is how I’m describing it as well. First problem: it’s only as good as the above.

2. Because of the above, its accuracy relies on probabilities. It can confidently give me wrong information, and as someone who would read this book to learn a topic I don't already know, I have no frame of reference to know whether I’m being fed accurate information.

3. Since it greatly speeds up the time it takes to physically write material, there is a possibility the author didn’t closely vet the information provided by the LLM as a next token predictor. That means it could be wrong in subtle ways, and the only way for me to know is to rely on knowledge I don’t have.

4. Had AI not been used, I could conceivably go on the past work of the author, rely on the person who has the expertise who wrote the forward, or the fact that physically writing a book takes prohibitively long enough that the dopamine from having written a book doesn’t outweigh the amount of time it takes, and if you are going to take months to years to write a book, you’re going to not want that effort to be in vain. You’re going to do your diligence and not just “wing it”.

AI makes it relatively trivial to appear knowledgeable and to get that dopamine rush from saying “I’m an author” and appearing to be an expert in a field without being an expert in a field. For some, that temptation is too great and there’s no way to know without the passage of time. Time for folks to review the book who know the subject matter. Time for reviews. Time for folks to put signs up that say “don’t trust this material.” In the meantime we still have that content out there, further infecting new AI models and people into believing it’s accurate.

That’s why the use of AI is dangerous, and is especially dangeorus without disclosure.

Sure, but you can build an agentic system which verifies outputs and fact corrects, with probably better accuracy than a human would.

As well, if people were a bit less anti-AI then maybe we can get disclaimers that things are written by AI that don't immediately torpedo any value the writing has.

As a professional mathematician it seems that AI is already at the point where, when well guided, it both does better research and writes better exposition than run if the mill mathematicians.

Well guided is a qualifier that matters.

In my opinion, doing good mathematics is very different from writing good exposition.

I have observed that models are not able to effectively come down to a human level. They are mediocre at approximating what a first-time reader would want to know. If you will forgive the anthropomorphization, they are not very empathetic. In this book for example, the author pauses the flow of thought with countless little anecdotes, anticipating where the reader might have a question or want to know more.

Of course, a well-guided AI is capable of anything a human is capable of. But is that not tautological?

I’d be surprised to see current LLMs write as well (and as non-annoying) as the writing in this book.

> What is the problem if it is AI written? Properly guided AI writes better than most human expositors.

I don't understand why HN cannot ever say the first sentence without the second one.

Most people agree that using AI for research or finding better words is fine, but then can't upvote or have a meaningful conversation because of the performative politics and wild delusions about a scifi future.

Dude, all we have with LLMs is an NLP search engine. Get over it. It's been around half a decade of this nonsense. There is no "step change". There is no "hockey stick" curve. The models have not "dramatically improved compared to last year" regardless of what year it currently is. There is no big bad overlord coming for you. Nobody is getting replaced by AI. Even frontier AI can't replace local AI. It's just the logical next step towards better search that assumes you want the "I'm feeling lucky" button a little too often.

That's not a fair comparison: I choose what I read not from the middle of humanity. I choose skilled writers. They write far better than AI. I'm through the opening volley of this book, and it is far better than the best AI prose I've read.

Tangent: I use AI for code, but I've had to ban it from writing readmes and doc comments; the AI models I've used produce text I'm unable to parse, and assume my readers would not be able to either.

I think a lot of it actually comes down to the perception of where the content came from. I brainstorm and riff with AI all the time, but I know what I am communicating with, I don't get the same sense of ickyness. Blogs and books and all these things that are claimed be to written by a human, but are actually just AI, is frustrating. Honestly, the content may be perfectly fine, but I feel something irritates humans when they think they have been deceived.

There was not a single real tangable way of determining this before AI Slop.

For sure it was less to review, less options but still.

So what did you use? I used things like Reviews, skimming through, getting a referal through a blog or hn and buying from reputational sources.

HN is a filter. Same as all the other things we have.

The author seems to have published math papers (as one can see on DBLP and other websites) and a PhD in maths. It gives me confidence that it's written by a human and also reading chapter 1 and chapter 2 I think there is a human behind it, not an LLM.

If it makes you feel better, I've known the author personally for over ten years, and he is both a human being and an excellent teacher. I'm about as confident as I could imagine being that he wrote this book himself. (In order for this to completely reassure you, you of course have to trust me, but I thought I'd add my vote of confidence just in case it helps even a little.)

This book aside, though, the fact that writing is no longer definitive evidence of human thought is one of the things I dislike the most about the LLM era. I very much share your sadness about that.

I feel the need to be clear; I have no reason to suspect the author of using AI; and am even a bit irritated for the author that I have to entertain these suspicions writ large now. It is unfair to the author who hasn’t done anything to warrant that suspicion, but it’s the world we live in at the moment.

I vocalize this feeling I have, not because the author has done anything to warrant it, but here, in this forum, we commonly have folks saying “so what if it’s AI?”, and by bringing up these feelings we have around the industry, we can have the conversation and (hopefully) have other folks think twice about whether they would use AI to write their book.

I want to read this book and have added it to my list of things to read; and your vouching for the author does help. One underlying issue I have (that is a me problem) is that I know nothing about this particular area, and therefore know nothing about the experts in this area, so I rely on human vouching.

Well, if we're going to have the conversation: so what if it were AI? Shouldn't the question be around correctness and good pedagogy? Shouldn't the question always be about vouching for those things? If it's actually done well (e.g. they were able to generate better illustrations than they otherwise could've), why exactly should someone think twice?

The author put his name and reputation to it. If it's excellent work, it's excellent work. If it's slop, it's slop.

I'm not the OP, but I can give my answer to this question, or at least one of my answers.

This book is presented as being written by a human. (In this case, a human I happen to know, which would add another dimension to my complaint, so let's imagine that weren't the case.) Maybe someday we'll live in a world where sticking a person's name at the top of a book doesn't carry the implication that they wrote the words in the book. That would make me sad for other reasons, but in any event, we don't live in that world right now, so for now, if you put a person's name on your book, you are claiming that that person wrote the book. If that's not true, you are lying, and like most people, I don't like being lied to.

Why does putting your name on it have to imply you wrote every word, and not instead, just attach your reputation to it, and say that you stand behind the words that are in it, regardless of who/what wrote the words? If we look at things that way, we can continue as we always have evaluating the content, pedagogy, etc. and associate good and bad content, pedagogy, etc with the author and know that when we see that author's name we'll know what we should expect (regardless of who wrote the individual words).

I'm imagining something more like the way we treat movie directors. When I see Michael Bay vs. Quentin Tarantino, I don't think that those people wrote the film, or set up every camera shot in minute detail, or designed the costumes, etc. but I know that they had a hand in arranging for all of that and it will all ultimately come through with their unique stamp on it.

You're proposing a new way that we could treat authorship that's different from how we currently treat authorship. There's an argument to be had about whether that would be better than our current system. My vote would be no, but I'm not claiming it's obvious one way or the other.

But regardless of whether you think your new system would be better, it's not the current system. Surely the question of whether someone is lying by putting their name on a book they didn't write can't depend on some hypothetical future change to the meaning of authorship that hasn't happened yet.

What do you mean "the" or "our" current system? That's entirely your interpretation, and we've always had a sliding scale of "non-authorship" from editors to ghostwriters. AI models are the same; you can use them in a heavily directed way (basically, as an editor, or in an outsourcing capacity for e.g. illustrations), or in a hands off way that you just endorse.

Editors can not say they are author.

> Maybe someday we'll live in a world where sticking a person's name at the top of a book doesn't carry the implication that they wrote the words in the book.

Not even an AI thing, we don't. Ghost writing has been going on for centuries.

I don't like that! I agree it's dishonest and I wish we lived in a world where having been exposed employing a ghostwriter is a disgrace no public figure can come back from. I don't like that AI has made it worse, either. At least with ghost writing there are some contexts (politicians, celebrity bios) where you might suspect it, but in most you won't.

But, we do live in that world right now.

Yeah, I'm also not a big fan of ghostwriting in the domains where it's prevalent. For what it's worth, though, academic writing is very much not one of those domains: taking LLM's out of it, if ten years ago it had turned out that the "author" of a math textbook like this one had paid someone else to write the whole book for them, that would be considered major academic misconduct and that person's reputation would have been pretty severely damaged. I do think it makes sense to take the norms of a particular subset of the publishing world into account when thinking about what a reasonable reader expects when they see someone's name on a book.

Human expertise and appeal to authority have long been a proxy for correctness and soundness in a body of work.

It's not a perfect proxy, but I'm usually going to trust a domain expert over the confident idiot who constantly lies to me, hides and downplays mistakes, and flits around opposing positions like a drunken moth.

At this time, if I see a text is AI generated, I have to assume it is unsound and possibly even nefarious. There is way too much information assailing my daily life that I have no other rational choice.

I answered this question elsewhere in this thread; here’s a link to it. https://news.ycombinator.com/item?id=50273553

That doesn't really answer anything though. There are tons of human cranks out there too who are perfectly willing to spend tons of time on their "theories." Humans make errors too. If you don't have a way to evaluate the source material or some endorsement from someone you have a reason to trust, then AI doesn't change that. If you do have an endorsement (e.g. Terence Tao says some AI book is extremely well done, or puts out his own book that he openly used AI to write), then why would you discard it because AI?

> The author put his name and reputation to it.

For at least the past 5 years, Amazon.com has been completely flooded with throwaway brand names churned out from random sequences of characters selling white-labelled products. The ones that do poorly get discarded and replaced, and the ones that find traction get to climb the rankings.

Do you think the same doesn't apply to "authors" of books, social media posts, and even academic papers in 2026? It doesn't matter if someone's staked their reputation unless their reputation is already widely known and trusted to begin with.

Well, this person claims on their website to have a PhD in math from CMU and to have taught the topic at multiple state universities. You could dig some into whether that's true, and then rely on the reputation of the named institutions if you don't know anything about them.

Just like reputation already worked. People have associations with each other. People endorse each other. Endorsements carry some transitive weight (I suppose you could use graph theory to model this). This has nothing to do with AI. Yes, Amazon is full of constantly changing "brands" with no reputation. That is different from a person or company that does have a consistent reputation that you can look up, even if you hadn't heard of them until today. Even Amazon also has e.g. Samsung or Asus if you don't want to buy AHIKJASFDIUHER.

The difference in the post-LLM era is that false identities can stand up a cohesive background and online presence with extremely little effort or human input, as many times as desired.

You took a cursory glance at a CV on a website and decided that was probably good enough to keep suspicion at bay, this time. But digging more and more to build up trust requires more time and effort than a bad actor trying to advance an agenda would need to put in; It is asymmetric.

> For at least the past 5 years, Amazon.com has been completely flooded with throwaway brand names churned out from random sequences of characters selling white-labelled products.

The last time I looked into someone's complaint on HN about Chinese companies setting themselves up on Amazon with nonsense data and no way to contact them nor any theoretical method of holding them to account for misbehavior, I went to the product link the complaining comment provided and discovered that it was offered by a company whose registered place of business (listed on Amazon!) was obviously the poor owner's personal home address.

Norman Cook was decades ahead of his time. (Fatboy Slim was just the moniker that happened to win the inflection point lottery).

I don't mind if it is written by a human or a machine, but AI has a way of writing things that are exasperating, with unnecessary detours around the point that have lately made me very intolerant of stuff for which in the past I had more patience. As soon as I see content that reads like AI slop, I feel like I am wasting my time watching paint dry, and I throw it away.

It's also often wrong.

But also, I would like money I spend to go to people, not tokens.

Even though I have no idea who you are, I appreciate your vote of confidence in the author. It matters. Thank you

Perhaps we’ll reach a point where humans might have to record themselves writing the things and publish this next to the work itself to prove it was human made.

You know this is easily verifiable right…. I just put 10 random pages into Pangram and they all came back 100% human. And now I feel bad for making an even greater proportion of comments on this thread not about graph theory.

How reliable are these test though?

My anecdotal experience has been that is is very reliable on inputs over 500 words. There are a number of third party evaluations that corroborate. Pangram is pretty easy to test for yourself if you are a skeptic.

Pangram is very good if you can provide enough text, in my experience.

I wouldn't use it as a 100% infallible AI detector when the stakes are high (accusing someone of cheating) but it's very good at detecting AI generated text when you can drop large sections of text into it.

Reading through the first chapter, I got the feeling that it is more human than a lot of the books you might find on O'Reilly or wherever. I totally support the use of AI to help with organizing material in better ways or creating different modalities for representation. I really hate when the book is very clearly just copy pasting the output of the LLM.

Also, saw your comment response, I do feel this very same guarding and unfortunately my instinct is to assume the content is AI, which is a disservice to all the people who are putting their hard effort into putting out quality things.

I have just taken this in stride but it has struck me a few times recently that everything I see now.. I basically have to classify it as to be immediately discarded or worth my time to even begin reading, and even if I do continue reading then I still have to be constantly evaluating if a person bothered to struggle with (write) it or not.

Quite frankly this is.. fucking terrible? Even worse, the end of something for humanity..?

IMO if i can learn from/enjoy the content then it makes no difference who/what wrote it. I'll even pay for it if I feel the content is equal in value to the price.

This is what I'm grappling with myself. I'm building out a bunch of materials for things I'm learning and feel like others can benefit from my trudging through and correcting or getting AI clarification.

I think we're quickly getting to a point where AI is going to be able to do a better job teaching things than humans can (especially stuff with heavy associations with paper/screens, like programming and math). AI can augment for personal styles and spin up whole entire educational widgets on demand. Human's can't scale like that.

I don't think there is educational worth in an novice publishing the outputs from their chats.

I think there is some worth in having someone knowledgeable using AI to generate educational material, although it will be in my opinion, of less use than if that knowledgeable person wrote the material by hand.

For example, many professors in universities have started generating slides or even assignments using AI. A knowledgeable teacher who cares about their students outcomes can generate better material.

There has been plenty of crap released in the past, and even in the AI age we should be able to look at the same signals to filter through it today.

While the author and book here seem trustworthy, the issue is real and likely more upon all of us. Nothing that we output will escape the same scrutiny, at least for a while until we will probably have own dedicated AI to scrutinize everything that gets in front of us

Putting aside whether or not the author used AI to write this - the concern here is that the content is accurate and correct, right? So suppose they did use AI to write it - your end goal is actually the same - you want a trustworthy, accurate, source of information.

In this sense AI does not actually detract from that - so long as there IS an author associated to the book, that author can build a reputation for thoroughly reviewed and high quality textbooks. So in the end, some authors will be known for a reputation for making good books, and the use of AI should give us access to a larger quantity of books, addressing more and more niche topics, for lower costs. So, this should be a good thing for education?

I'm very much just writing my thoughts down, but curious to know if others agree or disagree with this.

> the concern here is that the content is accurate and correct, right?

I think there's more, we just take it for granted because it's usually included. Imagine a teacher--perhaps a whimsical one in a Roald Dahl story--who is always very accurate and correct. However, somehow they always present things in a way that cripples students' future progress and understanding.

Most human communication involves some level of simulating the mind you expect was/will-be at the other end. This aspect becomes extra-important when teaching, because teaching about trying to change how that student-mind operates.

So the facts being imparted are secondary, and in many cases carefully incorrect facts must be used before you can introduce better ones.

> the concern here is that the content is accurate and correct, right?

> In this sense AI does not actually detract from that [...] that author can build a reputation for thoroughly reviewed and high quality textbooks.

The issue is a lot of the AI generated books out there aren't carefully reviewed and it being AI written is an early sign it's crap at the moment, and it's expensive cognitively to build a list of "trusted authors" or to know when searching if you're finding true reviews by people who can meaningfully evaluate the content of the book or if you hit an AstroTurf post fluffing the author.

The other indicator and thing that puts at least myself off is that if the author used AI significantly in the process they didn't care enough about writing it before to put the real human effort into writing it so the chances it's worth spending my real human time reading is low.

Let's say the book was written by AI. Can you you explain what makes you less excited about this stuff?

Like is there a concrete issue with the book you have?

Well, there would be a lot of credible-at-first-glance shite in it, which is rather damaging for an introductory textbook, so there's that.

I see a perfectly good, non-AI submission. Open the comments, and the top comment is about AI.

Can we not do this? I understand your sentiment, but ... can we not do this?

I get your sentiment, though the problem is older than AI, the convenience and market penetration has just ramped up the visibility in this arena.

Many books pre-ai were garbage but not at the rate they could be today. If anything people operate on greater discretion now than in the past because even the worst garbage still had a non-trivial barrier to entry, either sitting down to regurgitate your own garbage or paying someone to make some garbage for you.

There's also some historic precedence of this, the rise of Photoshop/CG and digital manipulation certainly led to a "is this photo real" to similar effect despite manipulations going back to the origins of photography. That acute concern was not as prevalent in my mind before editing became common and accessible.

I've asked myself this question as well.

Where I've landed -- once I get away from the distaste for load-bearing or a comment mentioning "spine" -- is that if the idea pushes me forward, challenges me towards improving, or otherwise informs, I'm okay with AI assisted writing.

I'm not okay with formulaic garbled nonsense, that annoys me!

AI tech is hitting our lives harder and faster than any tech before, and this has social and psychological side effects. society at large will struggle to recognize this, much less find healthy andeffective ways to adapt.

the erosion of trust will be socially catastrophic.

remember a time where you might admire a photo not just for its beauty, but for the good luck and skill of the photographer who captured it?

photoshop made us skeptical about truth, but AI will simply make it hopeless to ascertain truth.

note that i use AI extensively. i am hyper aware of the way it has impacted me, my peers, and my career, and im deeply concerned about how it will impact everyone as it is increasingly made "non-optional" by the rich and greedy who stand to benefit most from it.

I'm two chapters in now and if AI wrote this well we'd be much less pissed off about it.

This type of page recommendation is precisely what I have been visiting this website for almost two decades. Thank you

Same, too bad that recently (based on my hunch) these gems are getting less attention and LLM BS (or AI) is dominating the scene.

Cool. I am applying to jobs and it seems graph theory is popular in the "Leet Code" questions pace. So very timely, thank you! And clever domain name :)

I have studied algorithms in college. I believe the goals of leetcode vs the goals of graph theory may be against each other.

A good graph theory course abstracts away the details of code and pursues the goal of understanding how many problems can be expressed concisely and clearly through graphs.

A good leetcode practice ... honestly just hones how patient you are in debugging and memorising various code patterns.

If you want to pursue money, it's almost always better to pursue leetcode exclusively

This is not true.

Graph theory and algorithm engineering overlap a great deal. And not only in the directly graph theoretic terms like BFS, Dijkstra, Flow, etc, but also in that you need a good grasp of greedy algorithms, dynamic programming, divide and conquer, and several other general techniques.

You don't need to be a good algorithm engineer to secure a high-paying job though. In fact high-paying jobs regularly turn away strong algorithm engineers because they can't pass leetcode challenges.

The advice is sound -- if you want money focus on the flashy buzzword thing, not the actually useful thing.

I think their point is that there's a split between the modeling / mathematical focus versus an imperative algorithm focus.

Kind of like how being good at relational-databases and SQL is different than being good at coding up B-tree implementations.

Just use hashmap for everything.

Beautiful website and a breath of fresh air compared to the gitbook/vitepress typical styles these sorts of textbooks often go for.

not super fond of my memories of having to come up with a graph demonstration on a fixed time on a paper exam, but at least I can say I was once a person that could do that!

Feel like there's so much opportunity to combine great educational material with more interactive visualizations, given how easy it is to create great visualizations (with Claude, etc) nowadays. Especially in graph theory.

You would be surprised how hard it is to visualize arbitrary graphs. Basically, we can only render small highly regular ones in a neat way. Everything beyond that turns into a ball of wool.

Graphs in general are high dimensional structures and don't lend themselves to 2D projections. That is not a problem with coding the layouting algorithm. There simply is no good geometric arrangement for most graphs / networks because they are not planar [0], or even close to it (with few intersections).

[0]: https://en.wikipedia.org/wiki/Planar_graph

It's unfortunate that the book doesn't have solutions for practice problems. Which makes it hard to use for self-learning.

The book you want in this case is Gross, Yellen & Anderson, Graph Theory and its Applications, 3rd Edition.

There are plenty of ways to get a copy.

You can ask Claude for the solutions?

If you don't have the solutions, how do you verify Claude's work?

According to current practices, you ask ChatGPT or DeepSeek to verify it.

Turtles all the way down, I guess.

Everything, except the bleeding edge and situations requiring the context window to be more than 60% filled, are elementary to Opus 5.5 . If you provide the questions completely, you can be very sure that Claude’s solutions will be correct. The world has changed; AI is reliable; we need to adapt.

> The world has changed; AI is reliable; we need to adapt.

Yes, but I think it's important to state that it's only reliable for things that are very well known and extensively written about.

I get a lot of obviously wrong or slightly wrong answers from all LLMs across the board. If you don't double-check you just don't know or you might miss it.

And for the bleeding edge part: My godchild wanted to know the name of a Pokémon from his licensed shirt. One of the first ones, found in every training set. Couldn't get it right, was certain it was the wrong one.

> wanted to know the name of a Pokémon from his licensed shirt.

how did you even ask an AI this question? Took a picture of the shirt, uploaded it, and asked the AI what it was? That's a different class of problem than "answer this graph theory question and include your references: <paste text here>"

If you don’t understand the solutions, how can you verify textbook solutions? And sometimes they’re wrong, maybe subtle typos, causing hours of grief and feelings of inferiority.

You don't ask for proofs to print them out, put them in your drawer, and brag around that you own the proofs for these exercises.

You ask Claude for proofs to help your understanding. Understanding is the exact same activity as verifying.

The same way you'd verify a textbook's solution.

(Assuming it's a proof or something - if it's just a number - oh well).

Sure I can. But from my experience solutions in math books usually continue learning process and can provide even more insight to a problem. Solutions from ChatGPT or Claude barely can replace that.

(Edit) But I understand that goal of a book can be completely different. So it's just problem of my expectations.

For elaborating something unclear they're great tho.

all of the books I had in university basically just gave me the final result at the back of the book with no explanation, so I am quite jealous if this was your experience with textbooks. Could you name some of these books? They might be nice to buy!

Considering the fact that mainstream dev (aka boilerplate, route, orm, docker) might evaporate in the coming years. Is discrete math/graph theory a good starting point to pivot if software engineering is disrupted ?

math is arguably in a worse place than software

At the highest level it could be, but I can't see my future not learning more. So I'm trying to find a list of things that might still have some work value.

Yep, being able to understand more complex ideas and having frameworks for thinking/abstracting things will always be helpful. Graph theory is a great example.

Topp quality content!

I would even say that "Everyone Should Start Doing Graph Theory", but it's only my opinion of course. Take it or leave it.

https://vertex.degree/beginning/degrees#the-hypercube-graphs

I remember to this day the exact location I was when being introduced to construct hypercubes, to the exact bench in our uni cafeteria. It changed my understanding of multidimensionality completely.

Thanks for that, i was initials skeptical i would understand but this very clearly resembles the candidate paths for walkers in variatonal monte carlo simulation of spin systems. The edge set can be different, requiring "half filled" and flipping both a 1 and a 0 simultaneously. I'd not thought of these processes in terms of a graph, much less graphs which denote very high dimensional cubes with strange edges.

Has someone read this and Pearls in Graph Theory and can tell me which one they liked more as an intro? I found the former a lot of fun and was a good introduction for high school math grade. I saw a few problems and they looked just a bit beyond, but not by much! A bit of probability theory is well within e.g. Exercise 3 in the "The “cop-and-highway-robber game” asks the probability of a robber getting caught were they to choose an edge to rob and one of the vertices of that edge was chosen by a cop. Fun.

Tangentially related but spectral graph theory is one of the most beautiful topics I have studied. What's great about graph theory is that it is quite easy to understand but has devilishly hard problems. Ramsey numbers is an example.

If you like graph theory Dijkstra’s in Disguise is a great read: https://blog.evjang.com/2018/08/dijkstras.html

Hah Ok, added to Zenodo. I historically struggle with disciplines which have "Theory" in the name. The materials feel to me as an easy intro, then rapid cliff. We'll see! (I think my brain is genetically or otherwise not good at this level of abstracting)

*Zotero

AHH. Definition 1.4 and the questions after did it. It went from "Tracking all" to "I don't understand how this follows at all, and this makes no sense to me" 1.3b is a graph, not a union of two graphs?. What are the "two graphs"? What is this operator-like algebra, and what does it have to do with the rest of the definition or the text before and after it? A question about the complement which was never defined? Why are we probably agreeing that {1, 2} contain 3?

Update: Better phrasing I can understand:

"Definition 1.4. The union of two graphs G and H, denoted <>, is a single graph containing all vertices and edges from both. If G and H share no vertices in common, <> is a disjoint union."

For 1.5, I had no idea what the written definition meant, but this does: ``` Definition 1.5. The complement of graph G is the one that has the same vertices, two vertices are connected in G_complement if and only if they are not connected in G.

Please name PDF files of books something other than book.pdf

Pretty soon downloads folder starts to have book (n).pdf for 1..n

Oh this was a descent into past memories. I had the pleasure to take Graph Theory at UC Santa Cruz with Gerhard Ringel [1] way back when. Excellent instructor with some great stories.

[1] - https://en.wikipedia.org/wiki/Gerhard_Ringel

that background is so annoying to my eyes when scrolling the content, would be great if author can fix it

agreed, even as a graph background :(

Looks like an excellent book, and the author is right that graph theory is a very useful and practical branch of mathematics. If only I could persuade my son to read it.

comment section looks like it's filled with bots, a lot of commenters looking like they are giving their opinion as if they had read the whole pages, sometimes irrelevant

It seems the "Web server is down" for this link.

I prefer to do matrices. Thanks though.

You can do that too with spectral graph theory!

One more practical application: speech recognition sometimes uses a type of shortest paths search over a word or phoneme graph.

HN hug of death

This is so cool! love it

what applications is this useful for? node topology is already a solved problem for decentralized networks since most validators are on aws. unless this is for fun? theres finite space to order nodes topologically speaking tbh

For fun. All knowledge is beneficial, including what may not directly help with your job, but nonetheless will make you smarter and better at solving problems. This over-technical approach to knowledge is actually sad...

Graphs theory, like in general? Just as one example, an awful lot of numerical linear algebra research is devoted to the handling of sparse matrices (ones where most of the entries are zeroes), which can also be looked at as graphs. Likely any CAD program with a finite element analysis tool uses some graph theory under the hood.

In the age of LLMs, is this basically a hobby now. Since an LLM can implement and apply graph theory algorithms far better than any human can. “But the human needs to judge if it’s applicable”, that’s probably not true even in today’s models like Opus 5.5. It definitely does a better job than most humans at applying graph theory to prove theorems. It also does a good job of applying it to solve algorithms. So what’s the point of this intellectual activity?

More and more it feels like as humans we are re-entering the pre 1700s era where most humans never learnt any technical knowledge, circa they never needed it.

The LLM boosters will claim, this is good and fine, LLMs will create an age of miracles and we will climb the kardashev scale or whatever other nonsense. I don’t think that will happen, I’m like 99% sure we won’t even cure cancer. We’re just making large swathes of intellectual work that we invented since the 1700s to now redundant for some reason and hoping that’s a better future, we are liberated from the “toils of thinking”. Well humanity has lived for 1000s of years without thinking of any of this stuff, so we’ll be fine but I suspect the world was richer when we did think about all this.

This is great, graphs is also the answer to autonomous coding :D

How so?

We have experienced that adverserial review cycles is the only way to really guarantee good outputs from coding agents - best modelled as a cyclic graph.

I am even more confused after this answer: Are the nodes actual reviews or something else?

I don't think modelling this as a graph adds anything that you wouldn't get from the phrase 'adversarial review cycles' already. So graph theory is pretty much useless for this application.

Please prove me wrong.

what does neuron topology have to do with autonomous coding? MLP problem? doesn't make any sense

Reply on news.ycombinator.com