Let's think about planar trivalent graphs. (Or you can dualize and think about triangulations if you prefer.) It's easy to come up with a list of 'planar trivalent graphs with boundary' such that at least one graph on the list must appear as a subgraph of any planar trivalent graph.
As a first example, any planar trivalent graph contains a face with at most 5 edges, by an easy Euler characteristic argument. To simplify things a bit, let's just ignore graphs with faces with at most 4 edges ("small faces"), so we can say "a planar trivalent graph with no small faces contains a pentagon".
The next example, proved easily by the method of discharging, says "a planar trivalent graph with no small faces has a pentagon which is adjacent to either another pentagon or a hexagon".
What are all the "small" lists of subgraphs with this property?
It's relatively easy to keep modifying discharging rules and prove more and more complicated results of this form. Has anyone tried to do this exhaustively? (This particular context of planar trivalent graphs with no small faces would be particularly interesting, but answers for any type of planar graph would be good.)
Is there even a way to provably find all such "small" lists, for some sense of "small" (e.g. number of graphs in the list)?
