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