Изменения

для <tex>\forall \alpha,\beta \in \Gamma(G)</tex>. Поэтому отображение <tex>\alpha\rightarrow\alpha '</tex> является групповым гомоморфизмом группы <tex>\Gamma(G)</tex> на <tex>\Gamma_1(G)</tex>. Следовательно, <tex>\Gamma(G)\cong\Gamma_1(G)</tex> тогда и только тогда, когда ядро этого отображения тривиально.

Для доказательства необходимости предположим, что <tex>\Gamma(G)\cong\Gamma_1(G)</tex>. Тогда из неравенства <tex>\alpha\not=i</tex>(<tex>i</tex> — тождественная подстановка) следует, что <tex>\alpha'\not=i</tex>. Если в графе <tex>G</tex> существуют две различные изолированные вершины <tex>v_1</tex> и <tex>v_2</tex>, то можно определить подстановку <tex>\alpha\in\Gamma(G)</tex>, положив <tex>\alpha(v_1) = v_2, \alpha(v_2) = v_1, \alpha(v) = v</tex> для <tex>\forall v \not= v_1,v_2 </tex>. Тогда <tex>\alpha\not=i</tex>, но <tex>\alpha'=i</tex>. Если <tex>K_2</tex> {{---}} компонента графа <tex>G</tex>, то, записав ребро графа <tex>K_2</tex> в виде <tex>x = v_1v_2</tex> и определив подстановку <tex>\alpha\in\Gamma(g)</tex> точно так же, как выше, получим <tex>\alpha\not=i</tex>, но <tex>\alpha'=i</tex>.

Чтобы доказать достаточность, предположим, что граф <tex>G</tex> имеет не больше одной изолированной вершины и <tex>K_2</tex> не является его компонентой. Если группа <tex>\Gamma(G)</tex> тривиальна, то очевидно, что группа <tex>\Gamma_1(G)</tex> оставляет на месте каждое ребро и, следовательно, <tex>\Gamma_1(G)</tex> {{---}} тривиальная группа. Поэтому предположим, что существует подстановка <tex>\alpha\in\Gamma(G)</tex>, для которой <tex>\alpha(u)=v\not=u</tex>. Тогда степени вершин <tex>u</tex> и <tex>v</tex> равны. Поскольку вершины <tex>u</tex> и <tex>v</tex> не изолированы, их степени не равны нулю. Здесь возникает два случая.