Isomorphism Classes for Order 4 Size 3 Simple Graphs

From ProofWiki
Jump to navigation Jump to search

Theorem

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

Isomorphism-Classes-Order4-Size3-Simple.png


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