Cheap and Secure Web Hosting Provider : See Now

Necessities for two undirected graphs being isomorphic

, , No Comments
Problem Detail: 

As far as I know, for two undirected graphs $G = (V, E) $ and $H = (V', E')$, the following criteria is necessary for them to be isomorphic:

  1. $|V| = |V'|$
  2. $|E| = |E'|$
  3. $G$ has $j$ nodes of degree $k$ $\Leftrightarrow $ $H$ has $j$ nodes of degree $k$

Are there more that are that obvious? Thanks in advance for your help!

Asked By : Doc
Answered By : David Richerby

For two graphs $G$ and $H$ it is necessary for literally every property that holds of $G$ to also hold of $H$ and vice-versa. There's no point making a list because everything is in that list.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43653

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback