Manuscript IX-B-ST@1 · IX-B-ST.tex · theorem · f6af1523

Theorem: Eight unlabelled connected skeletons

Skeletons and the selected triangle · lines 712–746 · proof included or linked

IX-B-ST@1#thm:skeletons

Back to manuscript

Every connected loopless multigraph with at least one and at most three edges is isomorphic to exactly one of:

  1. a single edge;

  2. two parallel edges;

  3. a two-edge path;

  4. three parallel edges;

  5. a two-edge path with one edge doubled;

  6. a triangle;

  7. a three-edge path;

  8. a three-edge star.

Arbitrary graphs with at most three edges are disjoint unions of these with total edge count at most three, together with isolated vertices.

Proof. One edge forces two vertices. For two edges, connectedness permits either two vertices with a double edge or three vertices forming a path.

For three edges, connectedness permits at most four vertices. With two vertices there is a triple edge. With three vertices, either all vertex pairs are joined or exactly two pairs are joined, with multiplicities two and one. With four vertices the graph is a tree, whose degree sequence is either or . These are respectively a path and a star. Distinct listed vertex counts, multiplicities, or degree sequences distinguish the cases. Connected-component decomposition proves the last assertion.

Nearby in this section