Thread: set complements....

Hi, having big trouble with this one:

The

complement of a graph Z= (V,F) is the graph Z(bar)with
vertex set Qin which there is an edge between two vertices

x, y elements of

Qif and only if there is no edge between x and y in Z.
Suppose that the graph Z= (V,F) is self-complementary i.e.

Z

and Z(bar)are isomorphic.

1. Find a formula for |F| in terms of n = |Q|.

2. Prove that Zis connected.

Originally Posted by dannyshox

Hi, having big trouble with this one:

The

complement of a graph Z= (V,F) is the graph Z(bar)with
vertex set Qin which there is an edge between two vertices

x, y elements of

Qif and only if there is no edge between x and y in Z.
Suppose that the graph Z= (V,F) is self-complementary i.e.

Z

and Z(bar)are isomorphic.

1. Find a formula for |F| in terms of n = |Q|.

2. Prove that Zis connected.

If is the number of edges in graph of ordered then the number of edges in the complement is .

This is a standard theorem: At least one of or is connected.