On the groups of repeated graphs
Robert Frucht · Bulletin of the American Mathematical Society · 1949
In a recently published paper 1 Kagno showed that Pappus' graph, consisting of the 9 vertices A, B, C, D, E, F, G, H, I, and the 27 arcs AD, AE, AF, AG, AH, AI, BD, BE, BF, BG, BH, BI, CD, CE, CF, CG, CH, CI, DG, DH, DI, EG, EH, EI, FG, FH, FI, has a group of order 1296 which may be generated by the following set of eight substitutions: {ABC), {AB), (DEF), (DE), (GHI), (GH), (ADG)(BEH) (CFI), (AD)(BE)(CF).2 Kagno's proof of this fact (Theorem S) 1 is straightforward, but somewhat lengthy, and it seems of interest to note that this theorem follows at once from a more general and almost self-evident theorem on the groups of repeated graphs, if we apply to Pappus' graph the following lemma, also due to Kagno: 1 "If G' is the complement of G, then G and G f have the same group."3 Indeed the complement IF of Pappus' graph contains the 9 arcs AB, AC, BC, DE, DF, EF, GH, GI, HI; hence IF is not connected, but consists of three triangles (or complete 3-points) ABC, DEF, GHI; that is, II' is a threefold repeated triangle.To such a repeated graph we can apply the following theorem, which is of interest in itself apart from the use made of it here.THEOREM.If G is a connected graph of n vertices, having no simple loops, with a group & of order h, and if T is the graph consisting of m copies Gi, G 2 , • • • , G m of the same graph G, then the group of Y is Pôlya's "Gruppenkranz" ©m[^p], that is, the group of order m\h m and degree mn, whose substitutions may be described briefly as follows'.4 ' Let