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?
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
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP