Isomorphism Classes for Order 4 Size 3 Simple Graphs

Theorem

There are $3$ equivalence classes for simple graphs of order $4$ and size $3$ under isomorphism:

Proof

This article needs to be tidied. Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

The fact that the $3$ graphs given are not isomorphic follows from Vertex Condition for Isomorphic Graphs.

The vertices have degrees as follows:

Graph $1$: $2, 2, 1, 1$

Graph $2$: $3, 1, 1, 1$

Graph $3$: $2, 2, 2, 0$

The fact that there are no more isomorphism classes of such graphs can be proved constructively.

Let the $4$ vertices be named $A, B, C$ and $D$.

Lemma: There must be intersections among the edges.

Proof: If there were no intersection at all, it requires at least $3 \times 2 = 6$ vertices.

Without loss of generality, let $2$ of the edges be $AB$ and $AC$.

To place the last edge, there are $\dbinom 4 2 = 6$ potential choices:

$AB$: this makes the graph not simple

$AC$: this makes the graph not simple

$AD$: this is isomorphic to graph $2$

$BC$: this is isomorphic to graph $3$

$BD$: this is isomorphic to graph $1$

$CD$: this is isomorphic to graph $1$.

Hence, by Proof by Cases, these $3$ are the only isomorphism classes.

$\blacksquare$

Sources

• 1977: Gary Chartrand: Introductory Graph Theory ... (previous) ... (next): Chapter $2$: Elementary Concepts of Graph Theory: $\S 2.2$: Isomorphic Graphs