Detecting hallucinations in language models is a crucial step in ensuring reliable outputs, thereby increasing model trustworthiness in real-world implementations. To this end, we propose a novel approach towards hallucination detection in large language models (LLMs) that leverages the vast data capacity and semantic relationship modelling capabilities of knowledge graphs (KGs). By constructing a KG from an LLM-generated answer, we use this KG as a certificate for verifying the model output efficiently against an external KG. Our methodology integrates breadth-first search (BFS) and a natural language inference (NLI) model to enable real-time, schema-agnostic evaluation of LLMs which is applicable to both open- and closed-source domains. Furthermore, our approach is the first to evaluate answers requiring reasoning over complex graph structures, rather than relying solely on straightforward path-based inference.