Number of non-isomorphic ways the following graph can be labelled

827 Views Asked by At

In how many non-isomorphic ways can the following graph be labelled?

ignore the numbers on the graph

Ignore the numbers on the graph vertices.

I got two different answers and I'm not sure which one of my reasoning is right:

1) (5C2) ways to choose the 2 deg 3 vertices, 3 ways to choose the vertex of deg 2 connected to the two deg 3 vertices, and 2 ways to choose the two remaining vertices = 60

2) 5 ways to choose the vertex connected to the two vertices of deg 3, (4C2) ways to choose the two vertices of deg 3, and two ways to choose the remaining vertices = 60

3) Or (5C2) ways to choose the two vertices of deg 3, (3C2) ways to choose the two vertices of deg 2 at the bottom = 30

1

There are 1 best solutions below

4
On BEST ANSWER

The third way is wrong since it doesn't account for the two possible orderings of the two degree-2 vertices. The correct answer is $60$.

The way I figure it is to start with all possible labelings ($5! = 120$) and then divide by $2$ to account for the symmetry of reflection.