The fast development of quantum computing poses a threat to the security of the classical cryptographic system, and so there is a need to have strong post-quantum systems that are hard to break. The issue discussed in this paper is how to develop secure and efficient cryptographic protocols, taking advantage of graph-theoretic constructions that are not vulnerable to quantum attacks. The initial goal is to create a cryptographic scheme based on graphs and with hard problems like Graph Isomorphism, Hamiltonian Path and expander graph properties. The suggested methodology combines combinatorial graph structures with algebraic transformations, which are backed up by hybrid models that combine graph embeddings and lattice-based inspired security mechanisms. The synthetic and benchmark graph datasets are experimented on and the performance is measured based on the strength of security, complexity of computation and the scale. The suggested scheme has 97.1% accuracy in attack resistance, decreases the time of key generation by 21.4% and enhances the structural security measures by 18.6% over lattice-only schemes. Compares and contrasts to show improved resilience against quantum adversaries with efficiency. The innovation in the framework is that it integrates graph-theorically to design cryptography in a hybrid manner. This research goes a long way in enhancing the security of communication between IoT, cloud and distributed systems.