# graph theory Graph theory is a branch of discrete combinatorial mathematics that studies the properties of graphs and has applications including computer science. This is one page of public article previews, not the complete archive. Follow Next page to continue. Summaries are not the original full articles. ## Using LLMs with SMT Solvers for Automated Reasoning and Formal Verification DevFeed: [Using LLMs with SMT Solvers for Automated Reasoning and Formal Verification]() Original publisher: [Read original article]() Published: 2026-04-02T00:00:00Z Content type: opinion Language: en Sources: [Alex Korbonits]() Topics: [Automated reasoning](), [Large Language Model](), [Formal verification](), [Prompt Engineering](), [Claude](), [graph theory](), [Machine learning](), [Artificial Intelligence]() Tags: [automated-reasoning](), [claude](), [formal-verification](), [graph-theory](), [llm](), [prompt-engineering]() ### AI overview The author revisits a November 2023 idea about using Claude and prompt engineering to translate problems into propositions for an SMT solver, satisfy proofs, eliminate unknowns and quantifiers, and return results to an agent. The essay connects this idea to the author's background in formal logic, graph theory and machine learning, while noting that the concept was not novel in isolation. ### Source excerpt A November 2023 notebook entry about grounding LLMs with SMT solvers -- why formal verification might be the right fix for hallucination, and what it took to finally say it out loud. ## My Graduate Career in Math DevFeed: [My Graduate Career in Math]() Original publisher: [Read original article]() Published: 2025-05-12T18:35:57Z Content type: opinion Language: en Sources: [Jeremy Kun]() Topics: [Mathematics](), [Computer science](), [graph theory]() Tags: [computer-science](), [education](), [essay](), [essays](), [game-theory](), [graph-theory](), [group-theory](), [linear-algebra](), [math](), [mathematics](), [retrospective](), [topology](), [university]() ### AI overview An autobiographical essay about the author's transition from computer science to mathematics at Cal Poly, including university coursework, study abroad in Budapest, and reflections on the intellectual environment and an early group theory project. ### Source excerpt Editor's note: This essay was originally published on Medium on 2016-03-05. I have made minor edits in this republishing and added a few small retrospective notes. 2010-2011 (Year 0) I had just switched my major at Cal Poly State University from computer science to math. I wanted to double major but California was in a budget crisis and a few weeks before I tried submitting my double-major request the Provost for the CSU system put a blanket ban on double majors. ## A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details DevFeed: [A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details]() Original publisher: [Read original article]() Published: 2015-11-12T09:00:00Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [Algorithms, Complexity](), [graph theory](), [Computer science](), [math]() Tags: [algorithm](), [automorphism-groups](), [babai](), [breakthrough](), [complexity](), [computer-science](), [divide-and-conquer](), [graph-isomorphism](), [group-theory](), [johnson-graph](), [mathematics](), [permutation-groups](), [quasipolynomial](), [research]() ### AI overview This research-level blog post explains Laszlo Babai's claimed quasipolynomial-time algorithm for the Graph Isomorphism problem. Later updates report that an error was found, changing the result to sub-exponential time, followed by a claimed workaround restoring the quasipolynomial-time claim. ### Source excerpt Update 2017-01-09: Laci claims to have found a workaround to the previously posted error, and the claim is again quasipolynoimal time! Updated arXiv paper to follow. Update 2017-01-04: Laci has posted an update on his paper. The short version is that one small step of his analysis was not quite correct, and the result is that his algorithm is sub-exponential, but not quasipolynomial time. The fact that this took over a year to sort out is a testament to the difficulty of the mathematics and the skill of the mathematicians involved. ## When Greedy Algorithms are Perfect: the Matroid DevFeed: [When Greedy Algorithms are Perfect: the Matroid]() Original publisher: [Read original article]() Published: 2014-08-26T09:00:02Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [Algorithms, Complexity](), [graph theory](), [Graphs](), [math]() Tags: [algorithms](), [graph-theory](), [graphs](), [greedy](), [greedy-algorithm](), [kruskal-s-algorithm](), [linear-independence](), [matroids](), [minimum-spanning-trees](), [trees](), [vertex]() ### AI overview This article explains when greedy algorithms are guaranteed to produce optimal solutions. It introduces matroids as the framework characterizing that guarantee and uses the minimum spanning tree problem as an example, with background on matroid history and connections to linear algebra and graph theory. ### Source excerpt Greedy algorithms are by far one of the easiest and most well-understood algorithmic techniques. There is a wealth of variations, but at its core the greedy algorithm optimizes something using the natural rule, "pick what looks best" at any step. So a greedy routing algorithm would say to a routing problem: "You want to visit all these locations with minimum travel time? Let's start by going to the closest one. And from there to the next closest one. ## Anti-Coordination Games and Stable Graph Colorings DevFeed: [Anti-Coordination Games and Stable Graph Colorings]() Original publisher: [Read original article]() Published: 2013-09-09T09:00:00Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [graph theory](), [math]() Tags: [announce](), [anti-coordination](), [game-theory](), [games-on-graphs](), [graph](), [graph-coloring](), [graph-theory](), [network](), [np-completeness](), [paper](), [publication](), [research]() ### AI overview The author announces that a first paper on anti-coordination games and stable colorings has been accepted for publication. The article introduces the problem for a general audience, explaining how graph-based friendship networks affect interactions and raising questions about stability, convergence, centralized strategies, and computational difficulty. ### Source excerpt My First Paper I'm pleased to announce that my first paper, titled "Anti-Coordination Games and Stable Colorings," has been accepted for publication! The venue is the Symposium on Algorithmic Game Theory, which will take place in Aachen, Germany this October. A professor of mine once told me that everyone puts their first few publications on a pedestal, so I'll do my best to keep things down to earth by focusing on the contents of the paper and not my swirling cocktail of pride. ## The Erdős-Rényi Random Graph DevFeed: [The Erdős-Rényi Random Graph]() Original publisher: [Read original article]() Published: 2013-08-22T16:11:18Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [graph theory](), [math](), [Networks]() Tags: [color](), [combinatorics](), [erdos](), [giant-component](), [graph](), [graph-coloring](), [graph-theory](), [properties](), [random-graph](), [random-graphs](), [renyi](), [social-networks](), [structure]() ### AI overview This tutorial introduces the Erdős-Rényi random graph model G(n,p), in which each possible edge between n vertices is included independently with probability p. It discusses the model's role in combinatorics and network analysis, along with basic properties, applications, and computational exploration. ### Source excerpt During the 1950's the famous mathematician Paul Erdős and Alfred Rényi put forth the concept of a random graph and in the subsequent years of study transformed the world of combinatorics. The random graph is the perfect example of a good mathematical definition: it's simple, has surprisingly intricate structure, and yields many applications. In this post we'll explore basic facts about random graphs, slowly detail a proof on their applications to graph theory, and explore their more interesting properties computationally (a prelude to proofs about their structure). ## Depth- and Breadth-First Search DevFeed: [Depth- and Breadth-First Search]() Original publisher: [Read original article]() Published: 2013-01-22T11:44:27Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [Algorithms](), [Data structures](), [graph theory](), [Programming](), [Python]() Tags: [algorithms](), [breadth-first-search](), [computer](), [computer-science](), [data-structures](), [depth-first-search](), [graph-theory](), [graphs](), [mathematics](), [optimization](), [programming](), [python](), [queue](), [stack]() ### AI overview This tutorial introduces graph search through depth-first search and breadth-first search. It reviews directed graphs, vertices, edges, adjacency functions, and implementations of the basic graph data structure in mathematical terms and Python. ### Source excerpt The graph is among the most common data structures in computer science, and it's unsurprising that a staggeringly large amount of time has been dedicated to developing algorithms on graphs. Indeed, many problems in areas ranging from sociology, linguistics, to chemistry and artificial intelligence can be translated into questions about graphs. It's no stretch to say that graphs are truly ubiquitous. Even more, common problems often concern the existence and optimality of paths from one vertex to another with certain properties. ## Ramsey Number Lower Bound DevFeed: [Ramsey Number Lower Bound]() Original publisher: [Read original article]() Published: 2012-12-02T15:17:26Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [graph theory](), [Graphs](), [Mathematics]() Tags: [combinatorics](), [computational-complexity](), [graph](), [graph-coloring](), [graph-theory](), [mathematics](), [number-theory](), [probabilistic-method](), [ramsey-numbers](), [random-graph]() ### AI overview The article proves a lower bound for the diagonal Ramsey number R(m,m). By randomly coloring the edges of a complete graph, it shows that if binom(n,m)2^(1−binom(m,2)) is less than 1, there exists a coloring with no monochromatic m-vertex subgraph, so R(m,m) > n. ### Source excerpt Define the Ramsey number $ R(k,m)$ to be the minimum number $ n$ of vertices required of the complete graph $ K_n$ so that for any two-coloring (red, blue) of the edges of $ K_n$ one of two things will happen: There is a red $ k$-clique; that is, a complete subgraph of $ k$ vertices for which all edges are red. There is a blue $ m$-clique. It is known that these numbers are always finite, but it is very difficult to compute them exactly. ## Trees--A Primer DevFeed: [Trees--A Primer]() Original publisher: [Read original article]() Published: 2012-09-16T22:40:47Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [graph theory](), [Graphs](), [Algorithms](), [Learning]() Tags: [algorithms](), [graph](), [graph-theory](), [learning](), [mathematics](), [primer](), [programming](), [python](), [trees]() ### AI overview A primer on trees in graph theory. It defines trees as connected graphs without cycles, explains rooted-tree hierarchy, depth, leaves, and internal nodes, and introduces common algorithms on trees. ### Source excerpt This post comes in preparation for a post on decision trees (a specific type of tree used for classification in machine learning). While most mathematicians and programmers are familiar with trees, we have yet to discuss them on this blog. For completeness, we'll give a brief overview of the terminology and constructions associated with trees, and describe a few common algorithms on trees. We will assume the reader has read our first primer on graph theory, which is a light assumption. ## Handshake Lemma DevFeed: [Handshake Lemma]() Original publisher: [Read original article]() Published: 2012-01-29T22:24:31Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [graph theory](), [Mathematics]() Tags: [graph](), [graph-theory](), [handshake](), [mathematics]() ### AI overview The article proves the Handshake Lemma: in a party of n people, the number of people with an odd number of friends must be even. It uses double-counting to show that the sum of all friendship counts equals twice the total number of friendships, and then relates the result to graph theory. ### Source excerpt Problem: Prove or disprove: at a party of $ n$ people, there must be an even number of people who have an odd number of friends at the party. Solution: Let $ P$ be the set of all people, and for any person $ p \in P$, let $ d(p)$ be the number of friends that person has. Let $ f$ be the total number of friendships between pairs of people at the party. ## n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof) DevFeed: [n-Colorability is Equivalent to Finite n-Colorability (A Formal Logic Proof)]() Original publisher: [Read original article]() Published: 2011-09-04T22:41:27Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [graph theory](), [Math and Logic]() Tags: [completeness](), [graph](), [graph-coloring](), [graph-theory](), [logic](), [vertex]() ### AI overview A formal logic proof shows that an infinite graph is n-colorable exactly when every finite subgraph is n-colorable. The proof encodes valid colorings as propositional formulas and applies the Compactness Theorem. ### Source excerpt Warning: this proof requires a bit of familiarity with the terminology of propositional logic and graph theory. Problem: Let $ G$ be an infinite graph. Show that $ G$ is $ n$-colorable if and only if every finite subgraph $ G_0 \subset G$ is $ n$-colorable. Solution: One of the many equivalent versions of the Compactness Theorem for the propositional calculus states that if $ \Sigma \subset \textup{Prop}(A)$, where $ A$ is a set of propositional atoms, then $ \Sigma$ is satisfiable if and only if any finite subset of $ \Sigma$ is satisfiable. ## Graph Coloring, or Proof by Crayon DevFeed: [Graph Coloring, or Proof by Crayon]() Original publisher: [Read original article]() Published: 2011-07-14T22:24:13Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [graph theory](), [color](), [math]() Tags: [color](), [graph](), [graph-coloring](), [graph-theory](), [graphs](), [map](), [maps](), [mathematics](), [primer](), [pseudocode]() ### AI overview This tutorial introduces graph coloring through map-coloring examples, including the provinces of Costa Rica and the arrondissements of Paris. It models adjacent regions as vertices connected by edges, defines a valid graph coloring, and introduces the chromatic number as the smallest number of colors needed. ### Source excerpt How many colors are required to color the provinces of Costa Rica? A common visual aid for maps is to color the regions of the map differently, so that no two regions which share a border also share a color. For example, to the right is a map of the provinces of Costa Rica (where the author is presently spending his vacation). It is colored with eight different colors, one for each province. ## Teaching Mathematics--Graph Theory DevFeed: [Teaching Mathematics--Graph Theory]() Original publisher: [Read original article]() Published: 2011-06-26T16:19:20Z Content type: tutorial Language: en Sources: [Jeremy Kun]() Topics: [graph theory](), [Graphs](), [Mathematics]() Tags: [campolindo](), [education](), [google](), [graph-theory](), [introspection](), [mathematics](), [methods-of-proof](), [primer](), [puzzles](), [seven-bridges](), [seven-hills](), [teaching]() ### AI overview A mathematics teacher describes using puzzles and student-led discovery to introduce graph theory in high-school and middle-school lectures. The article presents the Seven Bridges of Königsberg problem as a central example and discusses mathematics as a non-linear process of questions, conjectures, and proof. ### Source excerpt Community Service Mathematics is supposed to be a process of discovery. Definitions, propositions, and methods of proof don't come from nowhere, although after the fact (when presented in a textbook) they often seem to. As opposed to a textbook, real maths is highly non-linear. It took mathematicians quite a lot of fuss to come up with the quadratic formula, and even simple geometric conjectures were for the longest time the subject of hot debate. ## Google's PageRank--A First Attempt DevFeed: [Google's PageRank--A First Attempt]() Original publisher: [Read original article]() Published: 2011-06-18T18:05:20Z Content type: article Language: en Sources: [Jeremy Kun]() Topics: [Graphs](), [graph theory](), [Web](), [Algorithm](), [Internet](), [structure]() Tags: [algorithm](), [analysis](), [eigenvalues](), [eigenvectors](), [google](), [graph](), [graph-theory](), [internet](), [mathematics](), [page-rank](), [ranking](), [search-engine](), [structure](), [vertex](), [web]() ### AI overview This post models the Web as a directed graph and introduces PageRank-style importance scoring for web pages. It first considers ranking pages by incoming-link counts, then explains why treating every link as equally valuable is inadequate and motivates weighting links by the importance of the linking page. ### Source excerpt The Web as a Graph The goal of this post is to assign an "importance score" $ x_i \in [0,1]$ to each of a set of web pages indexed $ v_i$ in a way that consistently captures our idea of which websites are likely to be important. But before we can extract information from the structure of the internet, we need to have a mathematical description of that structure. Enter graph theory.