1
$\begingroup$

By definition of graph isomorphism, it is apparent that two isomorphic graphs must have the same number of vertices, the same number of edges and the same degree of vertices. Is the following two graphs isomorphic?enter image description hereenter image description here. These two are bipartite graphs, but i am not sure whether i should call them isomorphic. Or, can i say that these two graphs are equivalent, i.e., fig.I=fig.II ?

$\endgroup$
6
$\begingroup$

These graphs are isomorphic; the bijection that exhibits the isomorphism is a reflection in the central horizontal axis.

If there is such a concept of equivalence of graphs distinct from isomorphism of graphs, I've never heard of it; Google also doesn't seem to know about it.

$\endgroup$
2
$\begingroup$

you have a simple graph, by definition: An isomorphism a simple graph G to is a simple graph H is a bijection $f: V(G) \rightarrow V(H)$ such that $ uv \in E(G)$ if and only if $f(u)f(v) \in E(H) $ then we say "G is isomorphic to H", written $ G \cong H$ Here you could give a direct bijection

$$ 1\rightarrow 5 $$ $$ 2\rightarrow 6 $$ $$ 3\rightarrow 3 $$ $$ 4\rightarrow 4 $$ $$ 5\rightarrow 1 $$ $$ 6\rightarrow 2 $$

This function is injective and surjective.

One other way you could start to analyse adjacency matrices. You will see that the applying row and columns permutation on A(G), you will get A(H), this also is a proof of the isomorphism.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.