This project explores the potential of large language models (LLMs) to solve complex graph theory problems, assessing their problem-solving, logical reasoning, and adaptability. Through tasks like graph coloration and isomorphism detection, the study evaluates how LLMs encode and process graph structures using innovative prompting techniques. The findings reveal current limitations in accuracy and task comprehension, while emphasizing the importance of task design, prompt structuring, and data selection. The project aims to inform future AI research, particularly in mathematical domains, and contribute to discussions about improving AI governance and the ethical development of advanced AI systems.