m i c h e l e c d

one more ?:

an undirected graph with n vertices that is isomorphic to it's own
compliment, must have how many edges

O(n^2) at most?
will that work?

thanks again

jim nastos

This isn't supposed to be a homework answer session.

No, probably not... It isn't specific enough. You should be able to get
a precise answer.
If a graph on 4 vertices has 0 edges, its complement has 6 edges (and
vice versa. If a graph on 4 vertices has 1 edge, how many edges does its
complement have? If it has 2 edges? And so on. Notice that if the graph is
isomorphic to its complement, it must have the same number of edges as its
complement.
Now generalize from 4 vertices to n vertices.

Next time you post homework problems, try explaining what you have
already tried, or how far in the problem you can get.

J

m i c h e l e c d

I will, thanks

--

M i c h e l e ' s M y o c a r d i u m:
D i g i t a l A r t G a l l e r y
http://micheles-myocardium.com/