Graph Theory

deathronan

Can someone help in how im supposed to go about doing this

"A tree is called homeomorphically irreducible if it has no vertices of
degree 2. Find all homeomorphically irreducible trees with 12 vertices.
(There are 26)"

I know what homeomorphically irreducible means, i just need a systematic way of finding all 26 trees

Cheers

Fremen

Seems like a lot of work. Here's what I'd do:

Draw one vertex, and designate it the "top" of the tree. Now consider the cases when the top has order N, for N = {1,...,11}, N not equal to 2. That's ten trees so far.
Do this recursively for all the layer two and layer three vertices (avoiding creating vertices of order two), and I would guess you'll get up to 26 different trees pretty quickly. The only trouble will be identifying isomorphic graphs (i.e. doubles)

hivizman

Fremen's approach is basically the way to do it, although you have to remember that some of the trees can have complex branching structures.

There's a full enumeration of all homeomorphically irreducible trees for up to 12 vertices here in Appendix II. It's worth doing the exercise for trees of fewer than 12 vertices as a build-up to the final problem, as this will give you an idea of how the various trees grow (sorry, couldn't resist it ).

deathronan

Cheers lads!

Fremen

What course is that you're taking? Seems well hard. Graph theory in UCD was a joke.

deathronan

Fremen wrote: »

What course is that you're taking? Seems well hard. Graph theory in UCD was a joke.

The module title is Discrete Maths 2 and im final year in Mathematical science and Computing in UL

The module was actually grand to be honest, thats the only assignment the lecturer gave us.