# Evaluating Large Language Models on Solved and Unsolved Problems in Graph Theory: Implications for Computing Education

arXiv: https://arxiv.org/abs/2602.05059 · HTML: https://mlsanity.com/paper/2602.05059/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 29 references that are in the map.
- First posted on arXiv 4 Feb 2026.

## Builds on (most cited first, 15 of 15)

- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Hallucination is Inevitable: An Innate Limitation of Large Language Models](https://mlsanity.com/paper/2401.11817/) (2024)
- [Large Language Models for Mathematical Reasoning: Progresses and Challenges](https://mlsanity.com/paper/2402.00157/) (2024)
- [LLMs Know More Than They Show: On the Intrinsic Representation of LLM Hallucinations](https://mlsanity.com/paper/2410.02707/) (2024)
- [Large Language Models for Education: A Survey and Outlook](https://mlsanity.com/paper/2403.18105/) (2024)
- [Practical and Ethical Challenges of Large Language Models in Education: A Systematic Scoping Review](https://mlsanity.com/paper/2303.13379/) (2023)
- [LLM Internal States Reveal Hallucination Risk Faced With a Query](https://mlsanity.com/paper/2407.03282/) (2024)
- [Premise-Augmented Reasoning Chains Improve Error Identification in Math reasoning with LLMs](https://mlsanity.com/paper/2502.02362/) (2025)
- [Large Language Models and Mathematical Reasoning Failures](https://mlsanity.com/paper/2502.11574/) (2025)
- [Enhancing Mathematical Reasoning in Large Language Models with Self-Consistency-Based Hallucination Detection](https://mlsanity.com/paper/2504.09440/) (2025)
- [FG-PRM: Fine-grained Hallucination Detection and Mitigation in Language Model Mathematical Reasoning](https://mlsanity.com/paper/2410.06304/) (2024)
- [TreeCut: A Synthetic Unanswerable Math Word Problem Dataset for LLM Hallucination Evaluation](https://mlsanity.com/paper/2502.13442/) (2025)
- [Unreflected Acceptance -- Investigating the Negative Consequences of ChatGPT-Assisted Problem Solving in Physics Education](https://mlsanity.com/paper/2309.03087/) (2023)
- [Reasoning Large Language Model Errors Arise from Hallucinating Critical Problem Features](https://mlsanity.com/paper/2505.12151/) (2025)
- [Theoretical Insights into Line Graph Transformation on Graph Learning](https://mlsanity.com/paper/2410.16138/) (2024)

## Built on by (most cited first, 1 of 1)

- [GTBench: A Curriculum-Grounded Benchmark for Evaluating LLMs as Mathematical Research Assistants in Graph Theory](https://mlsanity.com/paper/2606.03144/) (2026)

## Abstract (arXiv)

Large Language Models are increasingly used by students to explore advanced material in computer science, including graph theory. As these tools become integrated into undergraduate and graduate coursework, it is important to understand how reliably they support mathematically rigorous thinking. This study examines the performance of a LLM on two related graph theoretic problems: a solved problem concerning the gracefulness of line graphs and an open problem for which no solution is currently known. We use an eight stage evaluation protocol that reflects authentic mathematical inquiry, including interpretation, exploration, strategy formation, and proof construction. The model performed strongly on the solved problem, producing correct definitions, identifying relevant structures, recalling appropriate results without hallucination, and constructing a valid proof confirmed by a graph theory expert. For the open problem, the model generated coherent interpretations and plausible exploratory strategies but did not advance toward a solution. It did not fabricate results and instead acknowledged uncertainty, which is consistent with the explicit prompting instructions that directed the model to avoid inventing theorems or unsupported claims. These findings indicate that LLMs can support exploration of established material but remain limited in tasks requiring novel mathematical insight or critical structural reasoning. For computing education, this distinction highlights the importance of guiding students to use LLMs for conceptual exploration while relying on independent verification and rigorous argumentation for formal problem solving.