In this study, we introduce the concept of the K-Lexicographic Max Product (K−LMP) of neutrosophic graphs and explore its associated degree structure to enhance decision-making frameworks in food safety applications related to risk assessment, including freshness, contamination, and spoilage. Neutrosophic graphs, capable of handling indeterminacy, inconsistency, and incompleteness, provide a flexible mathematical foundation for modelling complex systems. By incorporating the K−LMP into neutrosophic graphs, we offer a novel approach to comparing and ranking food safety scenarios where multiple attributes and uncertain information coexist. We present example graphs and theorems related to K−LMP and further define the K-Lexicographic degree to quantify node significance within the context of neutrosophic graphs. To validate the practical utility of this approach, a food safety analysis is implemented, demonstrating how the model identifies critical control points and supports more robust, transparent decision-making under uncertainty. This work contributes to the advancement of neutrosophic graph theory and its interdisciplinary application in food quality and safety management.