January 2021

Show that knight’s cycles are impossible for the cases (a) and (b) in Theorem 1.4.7. (Case (c) is more difficult.) Hint: For case (a) use the ordinary coloring of a chessboard with black and white squares; for (b) use the same coloring as well as another appropriate coloring (say, in red and green squares) and […]

By Corollary 1.5.4, the complete graph  is not planar, as a planar graph on five vertices can have at most nine edges. The complete bipartite graph  has girth 4; this graph is not planar by Theorem 1.5.3, as it has more than eight edges. Show that the graphs which arise by omitting one edge e from either  or  are

Show that the Petersen graph is isomorphic to the complement of the triangular graph . The isomorphisms of a graph G to itself are called automorphisms; clearly, they form a group, the automorphism group of G. In this book we will not study automorphisms of graphs, except for some comments on Cayley graphs in Chapter 9;

Show that the automorphism group of the Petersen graph contains a subgroup isomorphic to the symmetric group S5. Hint: Use Exercise 1.5.11. What is the minimal number of edges which have to be removed from  to get a planar graph? For each n, construct a planar graph having as many edges as possible.

Let G be a graph. Carry out the following steps: (1) If G is not connected3 or if G contains a vertex of odd degree, STOP: the problem has no solution. (2) (We now know that G is connected and that all vertices of G have even degree.) Choose an edge e1, consider each permutation

A frequent problem is to order all permutations of a given set in such a way that two subsequent permutations differ by only a transposition. Show that this problem leads to the question whether a certain graph is Hamiltonian. Draw the graph for the case n = 3. The problem of finding Euler tours has

We want to find out in which cases the closed trail C0 constructed in Example 2.1.2 (2) is already necessarily Eulerian. An Eulerian graph is called arbitrarily traceable from v0 if each maximal trail beginning in v0 is an Euler tour; here maximal means that all edges incident with the end vertex of the trail

We construct a digraph G whose vertices are the single parts, modules, and finished products occurring in an industrial process. We want the edges to signify how many single parts or intermediary modules are needed for assembling bigger modules or finished products. That is, we assign weight w(i, j) to edge ij if we need

Show that an r-regular non-bipartite graph does not necessarily admit a 1-factorization, even if it has an even number of vertices. Hint: Consider the Petersen graph. Let G be a graph on 3n vertices. A 2-factor of G is called a triangle factor or a -factor if it is the disjoint union of n cycles

Decompose the graph K9 into _-factors. Hint: There is no cyclic decomposition as in Figure 7.2. Decompose the graph K6n−2 into 3-factors. Hint: Use Theorem 7.2.9. Readers interested in seeing more results on 1-factorizations and graph decompositions in general should consult the monographs [Bos90] and [Wal97].