0
$\begingroup$

For each of the pairs $G_1, G_2$ of the graphs in figures below, determine (with careful explanation) whether $G_1$ and $G_2$ are isomorphic.

enter image description here

For figure (a), two graphs have the same number of vertices and edges. They also have the same degree sequences. But, from this information we still can't conclude that they are isomorphic. Likewise the graphs in figure (b). So, what should I do to determine whether two graphs are isomorphic or not?

$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

HINT: The graph $G_1$ in (a) has a cycle of a length that is not the length of any cycle in $G_2$. The graphs in (b) are isomorphic; match up the vertices of degree $3$ in $G_1$ with those in $G_2$, and you shouldn’t have too much trouble matching up the rest of the vertices to construct an isomorphism between the two graphs.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .