# Number of vertices and edges of two isomorphic graphs

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?

• If the graphs are finite, then yes. I think by one-to-one correspondence they mean isomorphism. – Ashvin Swaminathan Jul 23 '16 at 16:38
• 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. – M. Vinay Jul 23 '16 at 16:38
• The very term 'one to one correspondence ' means bijection and two bijective sets have same cardinality. – Landon Carter Jul 23 '16 at 16:39
• @AshvinSwaminathan If by "isomorphism", you mean isomorphism of sets, that is a bijection, okay. – M. Vinay Jul 23 '16 at 16:40
• 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. – M. Vinay Jul 23 '16 at 16:43

$\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.