Действие группы на графе

[KhAl]

А вот контрпример более чем тривиальный. Всё, что было раньше, можно выкидывать в мусорку (и не читать).
В $S_4$ есть подгруппа $A_4$, она действует на $4$-х точках. Единственный граф, выдерживающий действие $A_4$ -- все рёбра одного типа. Его группа автоморфизмов -- $S_4$.

Кстати, графов на четырёх вершинах, у которых группа симметрий изоморфна $A_4$, вообще нет (даже без условия "выдерживает действие $A_4$").

[B@R5uk]

KhAl в сообщении #1602527 писал(а):

Единственный граф, выдерживающий действие $A_4$ -- все рёбра одного типа.

Добавьте к этому графу новую вершину и соедините её со старыми вершинами ребрами нового типа (например, типа "отсутствие ребра", если одиночных вершин в старом графе не было). Группа автоморфизмов нового графа будет та же. Получается контрпример к вашему утверждению.

[KhAl]

B@R5uk да, но Вы решаете не задачу ТСа.

-- 27.07.2023, 00:32 --

У него вершины графа заранее заданы, вместе с действием группы на них.