Count the graphs that have vertex set V = {1, 2, 3, ..., n}.

The problem is to let V = {1, 2, 3, ..., n}, and to determine the number of different graphs that can be formed with V as vertex set. See attached file for full problem description.

Prove that graphs that are isomorphic have the same number of vertices and the same number of edges, and that the degree of a vertex of a graph is equal to the degree of the image of that vertex under a graph isomorphism. Also, give an example of a pair of non-isomorphic graphs that have the same number of vertices and the same number of edges.

What does it mean for two graphs to be the same? Let G and H be graphs. We say that G is isomorphic to H provided that there is a bijection f:V(G) -> V(H) so that for all a, b, in V(G) there is an edge connecting a and b (in G) if and only if there is an edge connecting f(a) and f(b) (in H). The function f is called an isomorphi ...continues

Find the values of alpha and omega for the two graphs given in the attached file (45.4.doc).

The stability number, alpha(G), of a graph G is the cardinality of the largest subset S of V(G), the vertex set of G, such that no two of the vertices in S are connected by an edge of G. The clique number, omega(G), of a graph G is the cardinality of the largest subset S of V(G), the vertex set of G, such that every pair of ...continues

Let G, H be graphs such that G is a subgraph of H. Prove or disprove each of the following: (a) alpha(G) <= alpha(H) (b) alpha(G) >= alpha(H) (c) omega(G) <= omega(H) (d) omega(G) >= omega(H)

The stability number, alpha(G), of a graph G is the cardinality of the largest subset S of V(G), the vertex set of G, such that no two of the vertices in S are connected by an edge of G. The clique number, omega(G), of a graph G is the cardinality of the largest subset S of V(G), the vertex set of G, such that every pair of ...continues

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 e ...continues

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 ...continues

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 ...continues

Subgraphs

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