Марина's Journal

математика - задачка
в связи вот с этим разговором вспомнилась одна задачка, с которой я столкнулась лет десять назад. Тогда она была мне актуальна по рабочим делам, сейчас интерес уже чисто абстрактный, но почему-то все равно никто не хочет на эту тему поговорить. ;-)

Но тут много френдов-математиков, вдруг у кого-то будут идеи?

Представим себе графы, обладающие следующими свойствами:

- связные обыкновенные графы (т.е. без кратных ребер и петель) с конечным числом вершин;
- все вершины топологически эквивалентны - принадлежат одной орбите группы автоморфизмов;
- графы планарные, т.е., согласно теореме Куратовского, не имеют подграфов, гомеоморфных K_3,3 или K₅;
- степень всех вершин - либо 3, либо 4.

Какие это могут быть графы?

Сразу приходят в голову графы, "соответствующие" следующим выпуклым многогранникам:

- призмы (степень вершин 3) и антипризмы (степень 4), где основания имеют любое число вершин;
- платоновы тела (куб считается среди призм, октаэдр - среди антипризм, плюс еще тетраэдр и додекаэдр);
- архимедовы тела.

А еще что-нибудь есть? Особенно интересно про степень 3.

С одной стороны, других вершинно-транзитивных выпуклых многогранников вроде и нет. С другой стороны - а почему бы не существовать вершинно-транзитивным планарным графам, просто не имеющим столь же симметричных геометрических реализаций?

Вроде когда-то где-то была статья на смежную тему, но найти текст мне не удалось - да если бы и удалось, еще вопрос, смогла бы я его понять или нет.