# 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

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