Graphs with four vertices

Task number: 3594

Find all non-isomorphic graphs with four vertices.

For each of these, determine how many isomorphic counterparts it would have if the set of vertices were fixed (e.g. \(\{u,v,w,x\}\)).

  • Solution

    The graphs are in the following picture. Graphs above each other are mutually complementary; only the last group \(P_4\) is its own complement.

    Complementary graphs have isomorphism classes of the same size, which is given below.

    • There is one empty graph (every permutation of vertices gives the same graph).
    • There are six graphs with a single edge – we can choose a pair (i.e. an edge) from a four-element set in \(\binom{4}{2}=6\) ways.
    • There are twelve graphs isomorphic to \(P_3\cup K_1\) – there are four choices for the isolated vertex, and then three choices from the remaining vertices for the midpoint of \(P_3\).
    • There are only three matchings: there are three choices for the the neighbor of \(u\).
    • There are four graphs \(K_{1{,}3}\) – the choice is for the central vertex.
    • There are \(\frac{4!}{2}\) paths – each permutation gives an arrangement of vertices into a sequence, and two sequences yield the same graph if they are mutually symmetric.
  • Answer

    We can find 11 non-isomorphic graphs with four vertices.

Difficulty level: Easy task (using definitions and simple reasoning)
Solution require uncommon idea
Cs translation
Send comment on task by email