[ITGIRL]

Given the following graph, can you prove that it is not an isomorphic by showing that graph H doesn't match the property of graph G.

For example, Graph G has 8 vertices and 12 edges and Graph H has 8 vertices and 11 edges?

[ghostwalker]

(Original post by ITGIRL)


Given the following graph, can you prove that it is not an isomorphic by showing that graph H doesn't match the property of graph G.

For example, Graph G has 8 vertices and 12 edges and Graph H has 8 vertices and 11 edges?

Yes, that's fine. If they have a different number of edges, then they can't be isomorphic.

[ITGIRL]

(Original post by ghostwalker)
Yes, that's fine. If they have a different number of edges, then they can't be isomorphic.

Thanks. Also if one of the vertice has degree of 5 does that also hold that in the opposite graph it also should have a vertice of degree 5?

[ghostwalker]

(Original post by ITGIRL)
Thanks. Also if one of the vertice has degree of 5 does that also hold that in the opposite graph it also should have a vertice of degree 5?

If a vertex has degree 5, then under the isomorphism, the corresponding vertex must have degree 5 (it won't necessarily be the same vertex.).

One other test, for finite graphs is:

If you were to rank the degrees of the vertices in ascending order,
e.g. the graph on the left has (3,3,3,3,3,3,3,3), then any isomorphic graph must have the same combination. In this case, on the right (2,2,3,3,3,3,3,3), and hence they are not isomorphic.

Note this test is sufficient to show that the graphs are not isomorphic, but if the number sequences are identical, this is not sufficient to show that they are isomorphic.

[ITGIRL]

(Original post by ghostwalker)
If a vertex has degree 5, then under the isomorphism, the corresponding vertex must have degree 5 (it won't necessarily be the same vertex.).

One other test, for finite graphs is:

If you were to rank the degrees of the vertices in ascending order,
e.g. the graph on the left has (3,3,3,3,3,3,3,3), then any isomorphic graph must have the same combination. In this case, on the right (2,2,3,3,3,3,3,3), and hence they are not isomorphic.

Note this test is sufficient to show that the graphs are not isomorphic, but if the number sequences are identical, this is not sufficient to show that they are isomorphic.

Thanks for the claification, and the added descrption.