Only Respond if you are OTAs: 101478, 103846, 104591, 104455

Respond/pick up the credit if you absolutely know the solution is correct. If you can make an improvement on the solution in correctness, clarity, presentation, or if a proof can be more elegant, than please rewrite the entire solution.

Prove that in any graph...

Prove that in any graph with two or more vertices, there must be two vertices of the same degree.

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