Groups and Graphs: Proving Transitive Action on Vertices

  • Context: Graduate 
  • Thread starter Thread starter Mess10
  • Start date Start date
  • Tags Tags
    Graphs Groups
Click For Summary
SUMMARY

The discussion centers on proving that the automorphism group C of a regular graph R, with an odd number of vertices and a degree of at least 1, exhibits transitive action on the vertex set V. A user suggests assuming the contrary—that the action is not transitive on V—and deducing that R must be bipartite, leading to a contradiction. This approach confirms that C must indeed act transitively on V, reinforcing the properties of regular graphs.

PREREQUISITES
  • Understanding of regular graphs and their properties.
  • Familiarity with automorphism groups in graph theory.
  • Knowledge of bipartite graphs and their characteristics.
  • Basic concepts of transitive actions in group theory.
NEXT STEPS
  • Study the properties of regular graphs in detail.
  • Learn about automorphism groups and their applications in graph theory.
  • Investigate the characteristics and proofs related to bipartite graphs.
  • Explore transitive actions and their implications in group theory.
USEFUL FOR

Mathematicians, graph theorists, and students studying advanced topics in graph theory and group actions.

Mess10
Messages
1
Reaction score
0
Hi.

Need help with following problem:

Let R=(V,E) a regular graph with degree at least 1 and odd number of vertices.
Let C=Aut(R) the transitive action on the set E of R.

Prove C also transitive action on the set V of R.


Anyone got any idea/tips?

Thanks!
 
Physics news on Phys.org
Try assuming the contrary: that the action is not transitive on V. Deduce that R is bipartite. Contradiction. Am I missing something?
 

Similar threads

Undergrad Dfns group action & group, written in terms of the other
  • · Replies 26 ·
Replies
26
Views
2K
Undergrad Differences between left vs right actions in some group theory questions
  • · Replies 1 ·
Replies
1
Views
1K
Graduate When can transitivity emerge from cycle-suppressing dynamics?
  • · Replies 1 ·
Replies
1
Views
541
Graduate Vladimir I. Arnold ODE'S book, about action group
  • · Replies 4 ·
Replies
4
Views
3K
MHB Number of Orbits: Showing Equality of Group G and G_a
  • · Replies 34 ·
2
Replies
34
Views
6K
Undergrad Meaning of "passage to the quotient"?
  • · Replies 3 ·
Replies
3
Views
2K
Graduate Structure of modulo-integer matrix group GL(r,Z(n))?
  • · Replies 17 ·
Replies
17
Views
7K
MHB Prove the statements : Vectors/Matrices
  • · Replies 5 ·
Replies
5
Views
2K
Graduate Does Cayley's Theorem imply all groups are countable?
  • · Replies 8 ·
Replies
8
Views
3K
MHB Exponent of Group Hey! :o - Answers to Questions
  • · Replies 16 ·
Replies
16
Views
4K