Pythagorean neutrosophic set is an extension of a neutrosophic set which represents incomplete, uncertain and imprecise details. Pythagorean neutrosophic graphs (PNG) are more flexible than fuzzy, intuitionistic, and neutrosophic models. PNG are similar in structure to fuzzy graphs but the fuzziness is more resilient when compared with other fuzzy models. In this article, regular Pythagorean neutrosophic graphs are studied, where for each element the membership $(\mathfrak{M})$, and non-membership $(\mathfrak{N}\mathfrak{M})$ are dependent and indeterminacy $(\mathfrak{I})$ is independently assigned. The new ideas of regular, full edge regular, edge regular, and partially edge regular Pythagorean Neutrosophic graphs are introduced and their properties are investigated. A new MCDM method has been introduced using the Pythagorean neutrosophic graphs and an illustrative example is given by applying the proposed MCDM method.