Graph isomorphism

#isomorphism#bijection#invariant

Statement

Show that the path $P_4$ and the star $K_{1,3}$ are not isomorphic.

Hint

Compare degree sequences.

Show solutionHide solution

$P_4$ . Degrees: $1,2,2,1$ .

$K_{1,3}$ . Degrees: $3,1,1,1$ .

Non-isomorphic. Degree sequence is an isomorphism invariant; $1,2,2,1\neq3,1,1,1$ .

Conclusion. $P_4\not\cong K_{1,3}$ .