The involution principle

The involution principle

We have evaluated the number of graphs on v vertices by examining a certain action of the form _GY^X. We shall now give an example of the form _{H ´G}Y^X, i.e. a power group action. Afterwards we shall see how these two examples can be combined in order to prove an existence theorem for a certain class of graphs. While doing so we shall meet an interesting and useful counting principle which uses suitable actions of S₂, the smallest nontrivial group.

• Selfcomplementary graphs
• Involutions
• The Involution Principle
• The Principle of Inclusion and Exclusion
• The Garsia-Milne bijection
• Exercises

The involution principle