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.(adsbygoogle = window.adsbygoogle || []).push({});

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?

**Physics Forums - The Fusion of Science and Community**

Dismiss Notice

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# How to draw all subgraphs of K_5

Loading...

Similar Threads for draw subgraphs | Date |
---|---|

B Strategy for a Lottery-Style Draw Application | Jan 12, 2018 |

I Statistical problem of drawing colored balls from boxes | Apr 12, 2017 |

I Combinatorics problem on drawing sample with given mean | Sep 8, 2016 |

B Card-drawing probability problem | Aug 25, 2016 |

Graph theory - complete subgraphs | Feb 23, 2012 |

**Physics Forums - The Fusion of Science and Community**