This paper introduces a novel framework aimed at improving the clarity and dependability of explanations generated by AI systems specializing in Natural Language Processing (NLP). By employing a comprehensive graph-theoretical and mathematical methodology, the proposed model systematically enhances both the accuracy and reliability of AI’s explanatory functions. Central to this methodology is the Accuracy-Reliability Enhancement Framework (AREF), which utilizes graph theory to represent and analyze the AI decision-making process. This approach enables the identification and refinement of explanation pathways that maintain high fidelity and consistent reliability across various inputs. A specific objective function is developed to meticulously balance the need for high explanation fidelity and consistency against the complexity of the explanatory model. The framework leverages advanced mathematical capabilities of graph theory, including path analysis and optimization, node importance evaluation, and key subgraph identification. These features ensure that the explanations are not only transparent and easy to understand but also based on solid mathematical principles. By integrating graph-theoretical and mathematical approaches with the goals of Explainable AI (XAI), this approach significantly advances the development of AI systems that are both comprehensible and trustworthy, addressing a crucial need in contemporary XAI techniques through a clearly defined, mathematically rigorous strategy.