# If graph isomorphism is in P, is then P = NP?

I think that, since graph isomorphism is not known to be $$\textbf{NP}$$-complete, we can not reduce all problems in $$\textbf{NP}$$ to it, and therefore the implication does not hold.

Additionally, in the accepted answer to this question it is stated, that a proof that graph isomorphism is not $$\textbf{NP}$$-complete would prove $$\textbf{P} \neq \textbf{NP}$$. Why?

• If P=NP then every nontrivial problem in NP is NP-complete. – Yuval Filmus Jan 30 '19 at 16:30

We do know that $$\textbf{P} = \textbf{NP}$$ implies graph isomorphism is in $$\textbf{P}$$, but the other implication has not been proven (to the best of my knowledge). It is suspected graph isomorphism is $$\textbf{NP}$$-intermediate (i.e., it is in $$\textbf{NP} \setminus \textbf{P}$$ and not $$\textbf{NP}$$-complete). This question as well as this other one list evidences supporting said suspicions.
Regarding your second question: If $$\textbf{P} = \textbf{NP}$$, then any (nontrivial) problem in $$\textbf{NP}$$ is trivially $$\textbf{NP}$$-complete because any (nontrivial) problem in $$\textbf{P}$$ is $$\textbf{P}$$-complete (and we have assumed $$\textbf{P} = \textbf{NP}$$). Hence, by contraposition, if the conclusion of this implication is false (i.e., there is a problem in $$\textbf{NP}$$ which is not $$\textbf{NP}$$-complete), then the premise (i.e., $$\textbf{P} = \textbf{NP}$$) must also be false.