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 isomorphism of G to H. We can think of f as renaming the vertices of G with the names of the vertices of H in a way that preserves adjacency. Less formally, isomorphic graphs have the same drawing (except for the names of the vertices). Do the following: (a) Prove that isomorphic graphs have the same number of vertices. (b) Prove that if f:V(G) -> V(H) is an isomorph... click for more

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 vertices in S are connected by an edge of G. Two graphs, G and H, are given as figures in an attached .doc file (45.4.doc). Find the values of alpha(G), omega(G), alpha(H), and omega(H).

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 vertices in S are connected by an edge of G. 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)

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