1. ## 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 Q
in 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 Z
is connected.

2. 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 Q
in 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 Z
is connected.

If $|F|$ is the number of edges in graph $\mathcal{Z}$ of ordered $n$ then the number of edges in the complement $\overline{\mathcal{Z}}$ is $|Q|=n-|F|$.

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