Math 485, Graph Theory: Homework #1

Stephen G. Simpson

Due Wednesday, September 9, 2009

The assignment consists of exercises 12, 13, 14, 20, 22, 25, 26 on pages 14–18 of the textbook by West. Each exercise counts for 10 points. Here are some (rather sketchy) solutions.

12. Let P be the Petersen graph. Obviously P contains 5-cycles, hence is not bipartite.

An independent set in a 5-cycle is of size at most two. Since the vertex set of P is the union of two 5-cycles, it follows that any independent set in P is of size at most 4. (Inspection reveals an independent set of size exactly 4.) This gives another proof that P is not bipartite. Namely, bipartiteness of P would mean that the vertices of P can be partitioned into two independent sets. Since there are 10 vertices, at least one of the independent sets would have to be of size ≥ 5.

13. The graph in question is known as Q_{k}, the k-cube. To prove that Q_{k} is bipartite, color a k-tuple black if it contains an even number of 1’s, white otherwise.

Here is an alternative proof. We proceed by induction on k. Note that Q_{k+1} consists of two copies of Q_{k} with corresponding vertices joined by edges. If we use opposite 2-colorings of the two copies of Q_{k}, this gives a 2-coloring of Q_{k+1}.

14. In the 8×8 chessboard, each 1×2 or 2×1 rectangle consists of two adjacent squares of different colors. Consider the board obtained by removing two opposite corners. This leaves unequal numbers of black and white squares, so there is no way to partition them into 1×2 and 2×1 rectangles.

Here is a general statement. Let G be a bipartite graph. Can the vertex set of G be partitioned into adjacent pairs of vertices? A necessary condition is that the two parts be of the same size.

20. Graphs 1 and 3 are isomorphic. So far as I know, the only way to prove this is to explicitly exhibit an adjacency-preserving bijection of the vertices of graph 1 onto the vertices of graph 3. I leave this as a task for the student.

Graph 1 is not isomorphic to graph 2. One way to see this is to note that graph 2 includes a 4-cycle while graph 1 does not.

22. Graphs 1 and 2 are isomorphic by inspection (exchange the endpoints of the upper right outer edge). Graphs 1 and 5 are isomorphic by inspection (map the circle in graph 1 to the 7-pointed star in graph 5). Graphs 3 and 4 are isomorphic by inspection (move the center vertex to the top). Graph 3 contains a “crown” (a subgraph consisting of pair of adjacent vertices with 3 common neighbors), but graph 5 does not, hence graphs 3 and 5 are not isomorphic. This is one solution.

An easier solution is to look at complements and note that G ≅ H if and only if \overline{G} ≅ \overline{H}. For each of graphs 1, 2 and 5 the complement is a 7-cycle. For each of graphs 3 and 4 the complement is the disjoint union of a 3-cycle and a 4-cycle.

25. Let P be the Petersen graph. Clearly P has 10 vertices and is 3-regular. Corollary 1.1.40 (on page 13 of the textbook) tell us that the girth of P is 5. Thus P contains no 3-cycles and no 4-cycles.

We claim that P contains no 7-cycles. To prove this, let C be a 7-cycle in P. Since P is of girth 4, C must be an induced subgraph of P. (In other words, the only edges of P with both end vertices in C are the edges which belong to C.) Therefore, since P is 3-regular, each vertex of C must be adjacent to some vertex not in C. But then, because there are 7 vertices in C and 3 vertices not in C, at least three of the vertices in C must be adjacent to the same vertex not in C. Moreover, since C is a 7-cycle, some pair of these three vertices in C must be adjacent to each other. Thus we have a 3-cycle. This contradiction completes the proof.

26. Consider a graph G of girth ≥ 4 where each vertex is of degree k. Choose a vertex a_{1} in G. Let b_{1}, …, b_{k} be the k vertices adjacent to a_{1}. Since G is of girth ≥ 4, the vertices b_{1}, …, b_{k} are distinct from each other and nonadjacent to each other. Let a_{2}, …, a_{k} be the k − 1 vertices other than a_{1} which are adjacent to b_{1}. Since G is of girth ≥ 4, the vertices a_{1}, a_{2}, …, a_{k} are distinct from each other and nonadjacent to each other. They are also distinct from b_{1}, …, b_{k}, so clearly G has at least 2k vertices.

Now make the additional assumption that G has exactly 2k vertices. Since all of the vertices of G are of degree k, it follows that each of a_{1}, …, a_{k} is adjacent to each of b_{1}, …, b_{k}. Thus G is isomorphic to K_{kk}, the complete bipartite graph.