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
show comments
mcv
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.
show comments
namastasyai
This type of page recommendation is precisely what I have been visiting this website for almost two decades. Thank you
show comments
gortok
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!
show comments
armcat
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.
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 ?
show comments
itissid
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.
elxr
Beautiful website and a breath of fresh air compared to the gitbook/vitepress typical styles these sorts of textbooks often go for.
hackerbrother
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 :)
show comments
lopsotronic
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)
[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
holdingunsteady
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.
show comments
igleria
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!
paaloeye
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.
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.
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)
show comments
vorobeez
It's unfortunate that the book doesn't have solutions for practice problems. Which makes it hard to use for self-learning.
show comments
jmspring
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.
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.
throwaw12
that background is so annoying to my eyes when scrolling the content, would be great if author can fix it
show comments
GL26
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
dominicrose
It seems the "Web server is down" for this link.
wmichelin
HN hug of death
ImHereToVote
I prefer to do matrices. Thanks though.
offmutegame
This is so cool! love it
ultimaterr
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
show comments
sashank_1509
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.
cedarbyte482
This is great, graphs is also the answer to autonomous coding :D
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
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.
This type of page recommendation is precisely what I have been visiting this website for almost two decades. Thank you
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!
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
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 ?
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.
Beautiful website and a breath of fresh air compared to the gitbook/vitepress typical styles these sorts of textbooks often go for.
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 :)
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)
[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 ApplicationsFeel 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.
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!
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.
If you like graph theory Dijkstra’s in Disguise is a great read: https://blog.evjang.com/2018/08/dijkstras.html
Related HN thread: https://news.ycombinator.com/item?id=17745779
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)
It's unfortunate that the book doesn't have solutions for practice problems. Which makes it hard to use for self-learning.
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
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.
that background is so annoying to my eyes when scrolling the content, would be great if author can fix 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.
HN hug of death
I prefer to do matrices. Thanks though.
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
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