TransWikia.com

Prove that if G is isomorphic to H, then $alpha(G) = alpha(H)$

Mathematics Asked by Marconian on January 31, 2021

Prove that if G is isomorphic to H, then $alpha(G) = alpha(H)$

Considering that $alpha(G)$ is the independence number of a graph G, how can I prove if H is isomorphic to G, they have the same independence number?

One Answer

Simply consider an independent set $S$ in $G$ and push it through the isomorphism to get an independent set with the same cardinality.

Edit: going into more detail.

Let $f : V_G to V_H$ be a graph isomorphism. Let $S$ be an independent set of $G$. Consider $f(S) subseteq V_H$. Then $f|_S : S to f(S)$ is a bijection, so $|f(S)| = |S|$. And $f(S)$ is independent, since if we had an edge between $f(x)$ and $f(y)$ in $H$ for $x, y in S$ then we would also have one between $x$ and $y$ in the graph $G$.

Thus, if $G$ has an independent set of size $n$, so too does $H$. Then the independence number of $G$ is less than or equal to that of $H$.

Since $G$ is isomorphic to $H$, $H$ is isomorphic to $G$. Then by the same argument, the independence number of $H$ is less than or equal to that of $G$.

Answered by Doctor Who on January 31, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP