1
$\begingroup$

I am given the definition of graph isomorphism as follows:

Let $G$ be a graph with vertex set $V_G$ and edge set $E_G$, and let $H$ be a graph with vertex set $V_H$ and edge set $E_H$. Then $G$ is isomorphic to $H$ if there are one-to-one correspondences $$\alpha : V_G \rightarrow V_H \text{ and } \beta : E_G \rightarrow E_H$$ such that, for any edge $e \in E_G$, $$ e \text{ joins vertex } v \text{ to vertex } w \iff \beta(e) \text{ joins vertex } \alpha(v) \text{ to vertex } \alpha(w).$$ In this case, we write $G \cong H$.

From said definition, does it naturally follow that any two isomorphic graphs must have the same number of edges and vertices?

$\endgroup$
  • $\begingroup$ If the graphs are finite, then yes. I think by one-to-one correspondence they mean isomorphism. $\endgroup$ – Ashvin Swaminathan Jul 23 '16 at 16:38
  • $\begingroup$ The mere fact of $\alpha$ and $\beta$ being one-to-one correspondences ensure that $|V_G| = |V_H|$ and $|E_G| = |E_H|$, so yes. $\endgroup$ – M. Vinay Jul 23 '16 at 16:38
  • $\begingroup$ The very term 'one to one correspondence ' means bijection and two bijective sets have same cardinality. $\endgroup$ – Landon Carter Jul 23 '16 at 16:39
  • $\begingroup$ @AshvinSwaminathan If by "isomorphism", you mean isomorphism of sets, that is a bijection, okay. $\endgroup$ – M. Vinay Jul 23 '16 at 16:40
  • $\begingroup$ In particular, a graph isomorphism preserves every graph invariant (order, size, degree sequence, radius, diameter, connectivity, etc.), which is more than what an arbitrary bijection does. $\endgroup$ – M. Vinay Jul 23 '16 at 16:43
2
$\begingroup$

As already noted in comments:

$\alpha$ and $\beta$ are explicitly specified to be "one-to-one correspondences", which is a way of saying "bijections". Since there is a bijection between $V_G$ and $V_H$, they have the same number of elements. Similarly, since there is a bijection between $E_G$ and $E_H$, they have the same number of elements.

$\endgroup$

Your Answer

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