Neutrosophic sets (NSs) handle uncertain information while fuzzy sets (FSs) and intuitionistic fuzzy sets (IFs) fail to handle indeterminate information. Soft set theory, neutrosophic set theory, and rough set theory are different mathematical models for handling uncertainties and they are mutually related. The neutrosophic soft rough set (NSRS) model is a hybrid model by combining neutrosophic soft sets with rough sets. We apply neutrosophic soft rough sets to graphs. In this research paper, we introduce the idea of neutrosophic soft rough graphs (NSRGs) and describe different methods of their construction. We consider the application of NSRG in decision-making problems. In particular, we develop efficient algorithms to solve decision-making problems.