page_title: Pólya enumeration theorem
section_title: Graphs on three and four vertices
hierarchical_section_title: Pólya enumeration theorem / Examples / Graphs on three and four vertices
caption_attribution_description: English: This file represents all nonisomorphic simple graphs on four vertices. Türkçe: Bu dosya eşyapılı olmayan tüm dört köşeli basit çizgeleri göstermektedir.
context_page_description: The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by J. Howard Redfield in 1927. In 1937 it was independently rediscovered by George Pólya, who then greatly popularized the result by applying it to many counting problems, in particular to the enumeration of chemical compounds.
  The Pólya enumeration theorem has been incorporated into symbolic combinatorics and the theory of combinatorial species.
context_section_description: A graph on m vertices can be interpreted as an arrangement of colored beads. The set X of "beads" is the set of  possible edges, while the set of colors Y = {black, white} corresponds to edges that are present (black) or absent (white). The Pólya enumeration theorem can be used to calculate the number of graphs up to isomorphism with a fixed number of vertices, or the generating function of these graphs according to the number of edges they have. For the latter purpose, we can say that a black or present edge has weight 1, while an absent or white edge has weight 0. Thus  is the generating function for the set of colors. The relevant symmetry group is  the symmetric group on m letters. This group acts on the set X of possible edges: a permutation φ turns the edge {a, b} into the edge {φ(a), φ(b)}. With these definitions, an isomorphism class of graphs with m vertices is the same as an orbit of the action of G on the set YX of colored arrangements; the number of edges of the graph equals the weight of the arrangement.
  The eight graphs on three vertices (before identifying isomorphic graphs) are shown at the right. There are four isomorphism classes of graphs, also shown at the right.
  The cycle index of the group S₃ acting on the set of three edges is
  (obtained by inspecting the cycle structure of the action of the group elements; see here). Thus, according to the enumeration theorem, the generating function of graphs on 3 vertices up to isomorphism is
  which simplifies to
  Thus there is one graph each with 0 to 3 edges.
  The cycle index of the group S₄ acting on the set of 6 edges is
  (see here.) Hence
  which simplifies to
  These graphs are shown at the right.
caption: Isomorphism classes of graphs on four vertices.
exif: {}