How to draw all subgraphs of K_5

[christodouloum]

Hi all. I have a simple question on methodology for counting graphs explicitely. I am trying to find all trees of the complete graph K_5. I know that the answer is 5^(5-2)=125 and that each should have only four of the ten edges. I am trying to understand how I would draw them down by hand explicitely. It turns out difficult to be sure that I have exactly all of them without replications etc.

My simple way at it was to search for 25 graphs that would not coincide when the vertices are "rotated" and try to find first the ones with up to two valent vertices, then up to 3-valent and then up to four-valent vertices (all of these times five). I found respectively 14,6 and 1 which means I am missing four. Does anyone know of a systematic way to do this?

 

[Stephen Tashi]

Your post raises (in my mind) the general question of how to specifically enumerate combinatorial possibilities in graph theory. I searched the web, expecting to find that this would be a well developed mathematical/programming subject. I don't see any unified mathematical theory of it. The biologists and chemists are interested in algorithms that accomplish the task and if you search for "subgraph enumeration", you find specialized algorithms.

You particular problem would be interesting to discuss. Currently, I don't know the algorithm for it.