Give a formal proof that graph isomorphism is an equivalence relation 5 points H

Question

Give a formal proof that graph isomorphism is an equivalence relation

5 points How many unique graphs are there on n = 3 vertices? Draw all such graphs on n = 3 vertices and indicate which, if any, are isomorphic to each other 10 points

How many unique graphs are there on n = 4 vertices? Draw all graphs that are not isomorphic to each other (hint: there are 11 such graphs); indicate how many graphs on n = 4 vertices are isomorphic to each one of these.

3. In general, for an undirected graph with n vertices, how many unique graphs are there?

PLEASE BE THOROGH I really appreciate it.

Explanation / Answer

Answer to : How many unique graphs are there on n = 3 vertices?

" There are 4 graphs possible" To draw the graphs , please use pen and paper as per follows:

Answer to : How many unique graphs are there on n = 4 vertices?

There are 11 graphs possible.

Answer to "In general, for an undirected graph with n vertices, how many unique graphs are there?"

A graph with N vertices may have up to N*(N-1)/2 edges .

So overall number of possible graphs is 2^(N*(N-1)/2).

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.