Let $G$ and $H$ be isomorphic members of $\mathcal{G}_n$, let $\theta$ be an isomorphism between $G$ and $H$, and let $\alpha$ be an automorphism of $G$.
a) Show that $\theta\alpha$ is an isomorphism between $G$ and $H$.
b) Deduce tht the set of all isomorphisms between $G$ and $H$ is the coset $\theta\text{Aut}(G)$.
c) Deduce that the number of labelled graphs isomorphic to $G$ is equal to $\frac{n!}{\#\text{Aut}(G)}$
I was able to properly prove a and b, but I'm struggling to finish my proof for c.
Here's where I am for c:
Define $X(G) = \{G_0,G_1,\cdots,G_k \mid G \cong G_i, \forall 0 \leq i \leq k\}$, that is $X(G)$ is the set of all graphs in $\mathcal{G}_n$ that are isomorphic to $G \in \mathcal{G}_n$. The question now is to answer the value of $k$
Note that:
- From letter a it follows that if $G$ and $H$ are isomorphic, then $|\text{Iso}(G,H)| = |\text{Aut}(G)|$;
- $\text{Iso}(G,A) \cap \text{Iso}(G,B) = \emptyset$ if $A \neq B$.
Therefore
$$ \left|\bigcup_{i=0}^k\text{Iso}(G,G_i)\right| = k |\text{Aut}(G)| $$
Now I'm trying to use letter b in the following way:
$$ \bigcup_{i=0}^k\text{Iso}(G,G_i) = \bigcup_{i=0}^k \theta_{i}\text{Aut}(G) $$ where $\theta_i$ is an isomorphism from $G$ to $G_i$.
My approach is to use $n!$ as the cardinality of all the bijective functions from $\{1, \cdots, n\}$ to itself, that is the $S_n$ group.
It's a known fact that $\text{Aut}(G)$ is a group, and in our case it is also a subgroup of $S_n$ because $V(G) = n$ since $G \in \mathcal{G}_n$.
So if I'm able to prove that $\theta_{i}\text{Aut}(G)$ for all $0 \leq i \leq k$ are all the left cosets of $\text{Aut}(G)$ in $S_n$ then, from the fact that left cosets creates a partition, it'll follow that:
$$ \bigcup_{i=0}^k \theta_{i}\text{Aut}(G) = S_n \implies k |\text{Aut}(G)| = n! \implies k = \frac{n!}{\#\text{Aut}(G)} $$
But so far I haven't been able to prove this last statement.
Am I going in the right direction? What am I missing?
Thanks!
As a function, an element of $\operatorname{Iso}(G,H)$ for some $H$ is a bijection $f\colon\{1,2,\dots,n\} \to \{1,2,\dots,n\}$, or an element of $S_n$.
Going the other way, every bijection $f \in S_n$ is an element of $\operatorname{Iso}(G,H)$ for exactly one graph $H$. That's because having $f \in \operatorname{Iso}(G,H)$ for a known $f$ uniquely determines $H$: for every pair $\{v,w\} \subset \{1,2,\dots,n\}$, we must have $vw \in E(H)$ if $f^{-1}(v)f^{-1}(w) \in E(G)$, and $vw \notin E(H)$ otherwise. (Conversely, if $H$ is defined by this rule, then $f \in \operatorname{Iso}(G,H)$ must hold.)
Therefore if $G_1, G_2, \dots, G_k$ are the elements of $X(G)$, then the sets $\operatorname{Iso}(G,G_1)$, $\operatorname{Iso}(G,G_2)$, ..., $\operatorname{Iso}(G,G_k)$ are a partition of $S_n$. Part of this claim is the claim $\bigcup_{i=1}^k \operatorname{Iso}(G,G_i) = S_n$ that you're trying to prove, but it's also important that these sets of isomorphisms are disjoint. Then, we know that: $$\sum_{i=1}^k |\operatorname{Iso}(G,G_i)| = |S_n| = n!$$ Now, since part (b) tells us that $|\operatorname{Iso}(G,G_i)| = |\operatorname{Aut}(G)|$ for all $i$, we can solve for $k$ in terms of $|\operatorname{Aut}(G)|$ and finish the problem.