1. Problems for module

Definition 1: Two graphs: G = (V, E) and G' = (V', E') are called isomorphic if there is a one-to-one mapping f from V onto V' such that any two vertices v1, v2 V are adjacent iff f(v1) and f(v2) are adjacent.

Definition 2: The complement of a graph G has V(G) as its vertex set; two vertices are adjacent iff they are not adjacent in G. A graph G is called self-complimentary if G is isomorphic to .

Definition 3: The edge graph, or the line graph L(G) of a G is the graph with vertex set E(G) in which two vertices are adjacent iff they are adjacent as edges in G.

Problem 4: How different are these graphs?

Solution: The top three are the same, up to isomorphism; and the bottom three are the same up to isomorphism. The bottom three are not isomorphic to the top three.

Problem 5: Are the graphs below isomorphic? Explain.

Solution: The two graphs are not isomorphic, since the degrees of vertices in the left one are 4, while the degrees of the right one are 5.

Problem 6: Construct all non-isomorphic graphs with 4 vertices. Construct all non-isomorphic regular graphs with 4 and 5 vertices. Construct a 3-regular graph with 11 vertices.
Solution: The list of all non-isomorphic graphs with 4 vertices:

There are three regular graphs with four vertices.
There are exactly four regular graphs with five vertices. One such graph is of degree zero, the empty graph; the other one is the complete graph, whose degree is four; it is the complement of the empty graph. No 5-vertex graph of degree two is a 5-cycle; it is a self-complementary graph.

Problem 7: Determine wich pairs of the graphs below are isomorphic. Are any of these graphs isomorphic to ?

Solution: Graphs A, B, and C, but not D are isomorphic to .

Problem 8: Determine which pairs of the graphs below are isomorphic.

Solution: Graphs B and C are isomorphic and neither are isomorphic to A.

Problem 9: Determine which pairs of the graphs below are isomorphic.

Solution: Every vertex of A belongs to three triangles; some but not all vertices in B belong to three triangles; none of the vertex in C belongs to three triangles. Thus, A, B, and C are not isomorphic to each other. A is isomorphic to D.

Problem 10: The vertices of graph Ok are thek-element subsets of {1,2,...,2k + 1}. Two vertices are adjacent iff the are disjoint sets. Prove that

Problem 11: If G is self-complimentary, then |V(G)| is either 4k or 4k + 1 for some k 0.

Solution: If e and v are, respectively, the number of edges and the number of vertices of G, then for a self-complimentary G,
Therefore, 4e = v(v-1), which implies the result.

Problem 12: Construct all non-isomorphic graphs with five vertices. There are exactly 34.

Solution: This problem should be solved by writing a computer program. Such a solution is acceptable if the corectness of the program is checked.

Definition 13: A one-to-one mapping f : V(G) V(G) is called automorphism, if any two vertices x, y V(G) are adjacent iff f(x), f(y) are adjacent.

Problem 14: Construct a 3-regular graph with 12 vertices in which the identity is the only automorphism.

2. Degree sequences

Theorem 15: ( Erdös-Gallai, 1960) Let d = {d1, d2,...,dn) be the sequence of degrees of a graph G and let . Then is even and
The reverse is also true.

Theorem 16: (Havel and Hakimi, 1963) Let d = {d1, d2,...,dn) be a non-increasing sequence of non-negative integers. Denote d' the sequence {d2 - 1, . . . ,dd + 1 - 1, dd1 + 2, . . . , dn}. Then d is a degree sequence of a graph iff d' is.

Problem 17: Construct a graph with degree sequence {5, 3, 2, 2, 2, 1, 1}. There are four.

Solution:

Problem 18: How many are graphs with degree sequences {6, 6, 5, 4, 3, 3, 1}?

Solution: None.

Problem 19: How many are graphs with the degree sequences {7, 6, 5, 4, 3, 2}?

Solution: None.

Problem 20: Show that the edge graph L(G) has |E(G| vertices and
edges.

3. Decomposition of graphs

Definition 21: If G and H are vertex-disjoint graphs then

- the union G H is the graph V(G) v(H), E(G) E(H));
- the join G + H is the graph obtained from G H by adding all edges (v, u) where v V (G) and u V(H).
- the product G x H is the graph F with V(F) = V(G) x V(H) and E(F) = {((v, u1), (v, u2))} {((x1, y), (x2, y))}, where (u1, u2) E(H), v V(G) and y V(H), (x1, x2) E(G)).
- the Cartesian product G H is the graph F with V(F) = V(G) x V(H) and E(F) = {v1, u1), (v2, u2))} where ((v1, v2) E(G) and (u1, u2) E(H).

Definition 22: A decomposition of a graph is a list of subgraphs such that each edge appears in exactly one subgraph in the list.

Problem 23: Prove or disprove:

Problem 24: How to represent a hypercube (or an n-cube) Qn using the product operation?

Problem 25: Decompose K5 into two 5-cycles.

Problem 26: Decompose K7 into seven K3.

Problem 27: Decompose P (Petersen graph) into three connected subgraphs that are pairwise isomorphic.

Problem 28: Prove that if Kn decomposes into triangles, then either n - 1 or n - 3 is divisible by 6.