2.8 Degrees & Isomorphism | 2.8 Degrees & Isomorphism | Unit 2: Structures | Mathematics for Computer Science | Electrical Engineering and Computer Science

<Isomorphic Graphs
2.8.1Degree: Video
2.8.2Counting Degrees & Edges
2.8.3Isomorphism: Video
2.8.4Isomorphism
2.8.5Extreme Graphs
2.8.6Isomorphic Graphs
2.8.7Non-Isomorphic Graphs
>Coloring & Connectivity

Non-Isomorphic Graphs

Let's call the graph on the left \(G \) and the graph on the right \(H \). The two graphs are not isomorphic. Indicate which of the following assertions can prove this fact.

\(H\) has a vertex of degree 4, but \(G\) does not.

\(u_1\) has degree 3, but \(v_1\) has degree 2.

\(G\) has four vertices of degree 3, but \(H\) has only two vertices of degree 3.

\(G\) has a vertex named \(u_1\), but \(H\) does not.

\(G\) has three vertices that form a right triangle, but no three vertices of \(H\) form a right triangle.

\(G\) has an edge that is incident to two vertices of degree 3, but \(H\) does not.

Note that the last assertion mentions properties that are preserved under isomorphism, and so if it were true, it could prove that \(G\) and \(H\) are not isomorphic. Unfortunately, this assertion isn't true; both graphs actually have an edge that is incident to two vertices of degree 3.