Do the following: (a) Show that the graph G = ({a, b, c, d}, {ab, bc, cd}) is self-complementary. (b) Find a self-complementary graph with five vertices. (c) Prove that if a self-complementary graph has n vertices, then either n is congruent to 0 (mod 4) or n is congruent to 1 (mod 4).

Let G be a graph. Then G = (V, E), where V and E are the vertex set and edge set, respectively, of G.

The complement of G, which we will refer to as "G bar," is the graph (V, E bar), where V is the vertex set of G bar (i.e., the vertex set of G bar is identical to the vertex set of G) and E bar is the edge set of G bar. The edge set E bar is defined as follows:

For distinct vertices v1, v2, there is an edge that connects v1 and v2 in G bar if and only if there is no edge that connects v1 and v2 in G.

Definition: A graph G is self-complementary if G is isomorphic to G bar.

Do the following:

(a) Show that the graph G = ({a, b, c, d}, {ab, bc, cd}) is self-complementary.

(b) Find a self-complementary graph with five vertices.

(c) Prove that if a self-complementary graph has n vertices, then either n is congruent to 0 (mod 4) or n is congruent to 1 (mod 4).

Attached file(s):

45.7.doc  View File