Graph theory has become a pivotal area of research due to its broad applications in fields such as biochemistry (genomics), coding theory, communication networks, and cyber security. Recently, its integration into cryptography has garnered significant attention. This paper reviews the various ways in which graph theory is applied to cryptography, focusing on cryptographic algorithms that leverage general graph theory concepts, external graph theory, and expander graphs. In addition, we explore the potential of graph-theoretical models in enhancing cryptographic primitives, such as secure key exchange protocols, digital signatures, and encryption schemes. A novel perspective is presented on how graph theory could be used to construct new types of cryptographic systems with increased security and efficiency. Furthermore, we discuss emerging trends, including the use of quantum-resistant graph-based cryptographic protocols and the role of random graphs in improving the scalability of cryptosystems. This paper highlights the promising synergy between graph theory and cryptography and suggests future research directions to optimize these interdisciplinary approaches.