2
$\begingroup$

How many pairwise non-isomorphic simple graphs are there of 60 points and 1768 edges?

I'm having some trouble trying to figure this one out. Is there a general solution to solve this? Previous posts said to draw graphs, but I feel that it's pretty difficult to do realistically given the number of points and edges.

$\endgroup$
2
$\begingroup$

Hint 1: How many edges total are possible in a simple graph with 60 points?

Hint 2: Consider the graph complement. How many edges would any graph complement of a graph with 60 vertices and 1768 edges have?

Hint 3: How many graphs on 60 vertices exist with only two edges?

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Hint: The complete graph on $60$ vertices has $${60\choose 2}=1770$$ edges. How many ways can you remove 2 edges and be left with non-isomorphic graphs?

| cite | improve this answer | |
$\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.