In the movie Good Will Hunting the opening math problem is:
- Display all homeomorphically distinct irreducible connected simple acyclic graphs (trees) of size $n =10$
Recall that a tree (acyclic graph) is a graph without loops. "Irreducible" means that there are no vertices of order 2... that is, no vertices that can be eliminated, its edges linked, and the rest of the graph remains unchanged. "Homeomorphically distinct" simply means that the graph layout or embedding into the plane does not matter. "Simple" means at most one edge between any two vertices and no "loops" (edges from a vertex to itself). "Connected" of course means that there is a path from any vertex to any other vertex through the graph.
It turns out that there are 10 such graphs in the solution set, including these three:
What is the tersest Mathematica code that generates all 10 graphs? The tricky part for me is the condition of irreducibility, as there seem to be no simple function calls to identify or eliminate reducible graphs.
VertexDegree, of course, will help here.
My preference would be for some generative algorithm, but I suspect the tersest is to generate many candidate graphs and select the solution graphs among them.
I'd love to have code that naturally generalizes to arbitrary $n$, but that isn't part of this problem.