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... click for more

Context Free Grammar Problem

Please see attached...sorry looks to be an html problem.

Grammar Induction

Consider the grammar 1) -> |epsilon 2) -> 0|1|2|3|4|5|6|7|8|9 Use induction to show that the number of strings in L() of length n is equal to 10^n

Binary Tree Induction

# Recall that a binary tree can be defined recursively as * A Binary Tree is either empty * or A Binary Tree consists of a node with a left and right child both of which are Binary Trees. The degree of a node in a tree is equal to 0 if both children are empty, 1 if one of the children are empty, and 2 of both children are not empty. Use induction to show that the number of nodes in a binary tree is equal to one more than the sum of the degrees of the nodes in a binary tree.

Subgraphs

Let G be a complete graph on n vertices. Please calculate... (see attachment)