Find a graph G on five vertices such that omega(G) < 3 and omega (G bar) < 3, where "G bar" is the complement of G.

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

The clique number of G, omega(G), is the cardinality of the largest subset S of V such that every pair of vertices in S are connected by an edge 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.

Find a graph G on five vertices such that omega(G) < 3 and omega(G bar) < 3.

Attached file(s):

45.8.doc  View File