2
$\begingroup$

Let $S$ be a set of all graphs with 30 vertices and 432 edges. Find how many of them are mutually non isomorphic.

My approach: we can look at their complements instead. Since $K_{30}$ has ${{30}\choose{2}} = 435$ edges, complements therefore are graphs with 30 vertices and 3 edges.

Now I'm stuck. The answer should be 5, but I have no idea how to get to it. Can you nudge me towards the right direction?

$\endgroup$
2
$\begingroup$

Think about how many graphs you can make on a graph with $V = 30$ and $E = 3$. You could have a path with three edges, a path with two edges and a path with one edge, three isolated edges, a triangle, and a star.

$\endgroup$
0
$\begingroup$

The non-isomorphic 3-edge graphs without isolated vertices can be found by hand:

enter image description here

We can do this by:

  • Take an edge $K_2$.
  • Add an edge to it in all possible ways, giving $2K_2$ and the 2-edge path $P_2$.
  • Add an edge to $2K_2$ and the 2-edge path $P_2$ in all possible ways, to obtain the above.

From these we add isolated vertices until we obtain 30 vertices. This gives non-isomorphic 30-vertex 3-edge representatives. From these, we take the complement to obtain the non-isomorphic 30-vertex 432-edge representatives.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.