Irreducible Graphs

Abstract

A connected graph on three or more vertices is said to be irreducible if it has no leaves, and if each vertex has a unique neighbor set. A connected graph on one or two vertices is also said to be irreducible, and a disconnected graph is irreducible if each of its connected components is irreducible. In this paper, we study the class of irreducible graphs. In particular, we consider an algorithm that, for each connected graph $\mathrm{\Gamma }$, yields an irreducible subgraph $I(\mathrm{\Gamma })$ of $\mathrm{\Gamma }$. We show that this subgraph is unique up to isomorphism. We also show that almost all graphs are irreducible. We then conclude by highlighting some structural similarities between $I(\mathrm{\Gamma })$ and $\mathrm{\Gamma }$.