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 $\displaystyle |F|$ is the number of edges in graph $\displaystyle \mathcal{Z}$ of ordered $\displaystyle n$ then the number of edges in the complement $\displaystyle \overline{\mathcal{Z}}$ is $\displaystyle |Q|=n-|F|$.

This is a standard theorem: At least one of $\displaystyle \mathcal{Z}$ or $\displaystyle \overline{\mathcal{Z}}$ is connected.