SECTION 4.2 Basics of Group Theory 233
which has cardinality |H|. If G is partitioned into k such sets, then
obviously|G|=k|H|, which proves that|H| is a divisor of the group
orderG.
We summarize the above in the following theorem.Lagrange’s Theorem. Let Gbe a finite group and let H be a sub-
group ofG. Then|H|
∣∣
∣|G|.IfGis a finite group andg∈G, then we have seen thato(g) is the
order of the subgroup〈g〉that it generates. Therefore,
Corollary. IfGis a finite group andg∈G, theno(g)
∣∣
∣|G|.t tt t4
1
3
Example. Consider the graph given to^2
the right, with four vertices, and let G
be the automorphism group of this graph.
Notice that ifX={ 1 , 2 , 3 , 4 }, thenGis
a subgroup of Sym(X), the group of per-
mutations of of the four vertices. There-
fore, we infer immediately that |G| is a
divisor of 4! = 24.
Note that two very obvious automorphisms of this graph are the
permutations
σ:
1 2 3 4
↓ ↓ ↓ ↓
2 3 4 1
, τ :
1 2 3 4
↓ ↓ ↓ ↓
2 1 4 3
Next, note thatσ has order 4 andτ has order 2. Finally, note that
τστ = σ^3 (= σ−^1 ). Let C = 〈σ〉 and set D = 〈τ〉 be the cyclic
subgroups generated byσandτ. Note that sinceτ 6∈C, we conclude
that |G| > 4 = |C|; since by Langrange’s Theorem we must have
|C|
∣∣
∣|G|, we must have that|G| is a multiple of 4 and is strictly larger
than 4. Therefore|G|≥8. Also sinceGis a subgroup of Sym(X), we