A new study reveals that even the most advanced AI models falter when asked to reason about graph theory, a foundational area of mathematics that students and researchers rely on these systems to help them understand. Researchers have created GTBench, a specialized test that evaluates how well large language models (LLMs), or AI systems trained on vast amounts of text, can solve graph theory problems at different difficulty levels. The findings show a stark performance gap: while GPT-5 approaches near-perfect accuracy on introductory problems, all models, including GPT-5, degrade significantly when tackling graduate-level proof construction.

What Is Graph Theory and Why Does It Matter for AI?

Graph theory is a branch of discrete mathematics that deals with networks of connected objects, called nodes and edges. It underpins everything from social network analysis to algorithm design and network optimization. Unlike arithmetic or algebra, graph-theoretic reasoning requires a distinctive form of thinking: models must visualize abstract relationships, track the state of complex structures across multiple steps, and apply theorems carefully. This makes it an ideal stress-test for understanding whether AI systems can genuinely reason about relational structure or merely pattern-match answers.

Researchers and students increasingly rely on LLMs as reasoning assistants in their daily work. The gap between assumed and actual capability in a domain as foundational as graph theory carries real consequences for how these tools are trusted and adopted in academic and research settings.

How Does GTBench Evaluate AI Reasoning?

GTBench organizes 63 graph theory problems into three groups of increasing difficulty, mirroring how the subject is actually taught in universities. The benchmark draws on verified academic sources, including textbooks and university course materials, ensuring that problems reflect real-world educational standards.

• Group 1 (Undergraduate Introductory): Tests foundational knowledge such as standard graph families, degree sequences, subgraph operations, and basic counting arguments. These problems are predominantly definitional and have compact, verifiable answers.
• Group 2 (Undergraduate Intermediate): Requires application of graph algorithms and structural reasoning, including breadth-first search, depth-first search, spanning trees, and Eulerian and Hamiltonian conditions. Models must execute multi-step procedures and track intermediate states.
• Group 3 (Graduate-Level): Demands deeper mathematical justification and proof construction, involving advanced concepts such as graph coloring, planarity, matching, network flows, and NP-complete problems. These require comparative evaluation of multiple solution strategies.

What Did the Study Find About AI Performance?

The researchers evaluated five frontier models: GPT-5, Claude Sonnet 4.6, Gemini 2.5 Flash-Lite, Llama 3.3 70B, and Mistral Large 3. The results reveal a pronounced performance hierarchy that collapses as difficulty increases.

GPT-5 demonstrated the strongest performance, achieving 95.8% accuracy on Group 1 problems under zero-shot conditions, meaning it solved them without any examples or hints. However, even GPT-5's accuracy dropped to 82% on graduate-level proofs. All other models degraded substantially with difficulty. Most strikingly, Llama achieved 0% accuracy under human evaluation on Group 3 zero-shot problems, indicating that it could not construct valid graduate-level proofs at all.

The study also tested chain-of-thought prompting, a technique where models are asked to show their reasoning step-by-step. While this approach helped in some cases, it did not eliminate the performance gap between introductory and advanced problems.

What Types of Errors Are AI Models Making?

The researchers conducted a detailed failure mode analysis to understand where and why models go wrong. The patterns differ by difficulty level, offering insights into the nature of AI reasoning limitations.

• Execution Errors: In Groups 1 and 2, the most common failure is "correct algorithm, wrong execution." Models understand the right approach but make mistakes when carrying out the steps, such as miscounting or misapplying a rule.
• Incomplete Reasoning: In Group 3, models frequently produce incomplete reasoning, failing to fully justify their conclusions or leaving logical gaps in their proofs.
• Evaluator Disagreement: The study revealed systematic disagreement between human experts and automated judges, particularly on verbose or near-complete proofs. This suggests that evaluating advanced mathematical reasoning is inherently challenging and that current automated scoring methods may not capture the nuances of mathematical correctness.

Why Should Educators and Researchers Care About These Results?

The findings have direct implications for how AI tools are governed and deployed in mathematical education and scientific research. If students and researchers are using these models as reasoning assistants without understanding their limitations, they risk accepting incorrect or incomplete reasoning as valid. The study shows that while AI can reliably help with introductory material, it becomes unreliable at advanced levels where rigorous proof construction is essential.

The research also highlights a broader challenge: evaluating AI reasoning in domains where correctness is not always binary. In graduate-level mathematics, a proof can be nearly correct but still flawed, or verbose but ultimately sound. Current automated evaluation methods struggle with these nuances, as evidenced by the disagreement between human evaluators and LLM-as-judge scoring, which ranged from 48% to 83% agreement across human pairs.

GTBench provides the first curriculum-grounded evaluation framework specifically designed for graph-theoretic reasoning in LLMs. As AI systems become more integrated into academic and research workflows, benchmarks like this one are essential for understanding where these tools can be trusted and where human expertise remains irreplaceable.