2.7(a). 

Note:  G(3, 2) means the alphabet size is n = 3 (we’ll use A = {0, 1, 2}) and we want every string of length k = 2 to appear once in the de Bruijn sequence.  The vertex labels are strings of length k − 1 = 1 and the edge labels are strings of length k = 2. So the vertices are {0, 1, 2} and the edges are {00, 01, 02, 10, 11, 12, 20, 21, 22}.

(b) There are many possible answers. Form any Eulerian tour in the graph. Here is one example, but there are many more:

01         12        20        00        02        22        21         11         10

Take the last character of each vertex except the final one that closes it, to get ONE of many possible answers:  .

There are too many correct answers to list them all, but that doesn’t mean everything is a correct answer.  Correct answers will be strings of length 9, with three 0’s, three 1’s, and three 2’s; and each two-character trinary string 00, 01, 02, . . . , 12, 22 occurs once in it (possibly wrapping around the end, as with 10 in this example).

Common mistakes:

• Vertices as strings of length k=2 (giving 32 =9 vertices) instead of k − 1=1 (31 =3 vertices).

• Not properly converting a cycle to a de Bruijn sequence. Each vertex (or edge) adds its last character, not ALL of its characters. E.g., for the above cycle expressed in terms of edges, writing 01, 12, 20, 00, 02, 22, 21, 11, 10 instead of converting it to a de Bruijn sequence.

• When taking the last character of each vertex, you shouldn’t do it with the closing vertex, since that repeats the contribution of the initial vertex. So it’s 012002211, not 0120022110.

2.9. Let P = v1 ...vr  be a longest path in the graph. This has length r − 1 (count its edges).

Suppose there is a cycle C containing P .  If the cycle has more than r vertices, then we can remove one edge from C to get a path that’s longer than P ! So C must be C = v1 ...vrv1 .

Now, assume by way of contradiction that r < n.  Then one or more vertices of the graph are not in the cycle.  Since the graph is connected, there’s at least one edge {vi,w} where vi  is in the cycle and w is not (vi  ∈ V (C) and w ∈ V (G) \ V(C)).

Rotate C to represent it as C  = vivi+1 ...vrv1v2 ...vi.   Remove the first edge of C , vivi+1 , and add edge viw at the end to get P2  = vi+1 ...vrv1v2 ...viw.  This has one more edge than P , contradicting the assumption that P is a longest path. Thus, our assumption r < n is incorrect, so we conclude that r = n. Thus, cycle C has all vertices of the graph, so it’s a Hamiltonian cycle.

(Or, remove the last edge of C , vrv1 , and add edge wvi at the start to get P3 = wv1 ...vrvr+1 ...vr . We’re showing two ways for the answer key, but you only need P2  or P3.)

2

2.16. Let v1 ,...,vr  be a longest path in the graph (expressed in vertices).

The neighbors of vr  must be a subset of {v1 ,...,vr ─ 1 }, because if there is any other neighbor of vr, we could extend the path by at least one edge, contradicting that we selected a longest path. List the neighbors of vr  in the format vi1 ,vi2 ,...,vid, where 1 ≤ i1  < i2  < ··· < id  ≤ r − 1, and d = d(vr) ≥ δ(G) ≥ k .

We know vr ─ 1  is a neighbor of vr, since vr ─ 1 vr  is the last edge of the path.  So id  = r − 1.

We will show that the spacing between any two consecutive indices ij  and ij+1  is at least 2. Assume by way of contradiction that ij+1  = ij + 1 for some j = 1, 2,...,d − 1.  Then vij ,vij+1,vr forms a triangle:

• vijvij+1   = vijvij+1  is an edge of the original path

• vijvr  and vij+1vr  are edges because vij   and vij+1   are neighbors of vr .

But the graph has no triangles, so we have arrived at a contradiction.

Thus, ij+1 − ij  ≥ 2 for each j = 1, 2,...,d − 1.

Thus, i1  ≤ id − 2(d − 1) ≤ (r − 1) − 2(k − 1) = r − 2k +1.

We can truncate the path to vi1 vi1 +1 ··· vr  and then close it to form a cycle C , since vi1   is a neighbor of vr. The length of this cycle is r − i1 +1 ≥ (r +1) − (r − 2k +1) = 2k .

H-201. (a) The sum of degrees is 5 + 3 + 3 + 2 + 1 + 1 = 15, which is odd.  However, in a graph, the sum of degrees is twice the number of edges, hence even. So there is no such graph.

(b–d) The sum of degrees is even.  This doesn’t guarantee that the graphs exist, but it’s easy to exhibit such graphs.  Note that the graphs for (c) and (d) are unique up to relabelling of the vertices.  (b) has multiple answers possible; for example, any correct answer to (c) would also be a correct answer for (b) (but not vice-versa) since they have the same degree sequences and a simple graph is a special case of a multigraph.

(d)  1

4                        

3              

5

(e) There are many ways to do this.  One is to form a cycle on 7 vertices (1, 2, 3, 4, 5, 6, 7, 1), then add in an edge {8, 9}, and an isolated vertex {10}.

H-202. (a) An Eulerian trail starting and ending at different vertices requires exactly two vertices of odd degree. But all vertices have even degree (4), so there is no such trail.

However, there are lots of Eulerian tours. One example is 1, 3, 5, 1, 2, 4, 6, 2, 3, 4, 5, 6, 1.

Common mistakes:

• Mixing up Eulerian and Hamiltonian.

• Making a trail that starts and ends at different vertices, and uses all but one edge. But then it’s not Eulerian since it doesn’t use all edges.

(b) There are lots of Hamiltonian paths. One is 1, 2, 3, 4, 5, 6.

There are also lots of Hamiltonian cycles. One is 1, 2, 3, 4, 5, 6, 1.

(c) Path of length 4:  There are multiple answers possible.   One is  1, 5, 4, 3, 2, that is, the sequence of 4 edges {1, 5} , {5, 4} , {4, 3} , {3, 2}. No vertex is reused, so it’s a path.

Walk of length 4 from 1 to 2 that isn’t a path: One possible answer is (1, 5, 3, 1, 2), that is, the sequence of 4 edges {1, 5} , {5, 3} , {3, 1} , {1, 2}. It’s not a path since 1 is reused.

H-203. (a) There are ╱2(4)、=  = 6 pairs of vertices. A subset of these pairs is chosen as the edges, giving 2(2(4)) = 26 =  such graphs.

(b) Be careful: drawings that look different may represent the same unlabelled graph! With 4 vertices, there are up to ╱2(4)、= (4 · 3)/(2 · 1) = 6 edges.

• Graphs with 0 edges: All vertices isolated. One graph (Graph 1 in the drawing below).

• Graphs with 1 edge: Take any one edge and leave the other two vertices isolated.  One graph (Graph 2).

• Graphs with 2 edges: Either the two edges are touching or not (Graphs 3–4).

• Graphs with 3 edges:

– a “star” with three edges emanating from one vertex to each of the others (Graph 5);

– a path with three edges (Graph 6);

– a triangle plus an isolated vertex (Graph 11; complement of Graph 5, already listed).

• Graphs  with  4, 5, 6  edges:  The edges are complements of graphs with 2, 1, 0 edges. Complements are shown on the bottom row below. Note that Graph 6 and its complement are isomorphic, so there is not another one shown on the bottom for it.

(c) Be careful: labellings that look different may represent the same abstract graph G = (V, E).

• Graph 1:  Although there are 4! ways to assign labels to the four vertices shown in the drawing, they all result in V  =  {1, 2, 3, 4} and E  = ∅.   So they are all the exact same abstract graph G = (V, E). Thus, there is 1 way to label this class.

• Graph  2:  Choose two elements {a, b} out of {1, 2, 3, 4} in one of  ╱2(4)、ways.   Label the vertices of the edge as a and b in either order, and label the other two vertices with the remaining two numbers in either order.  Although it may appear there are two ways to assign a and b, and two ways to assign the other two labels, they all result in the same V = {1, 2, 3, 4} and E = {{a, b}}. So there are ╱2(4)、= 6 ways for this case.

• Graph 3:  Choose two elements {a, b} out of {1, 2, 3, 4} in one of ╱2(4)、= 6 ways, and let {c, d} be the other two elements.  We can label the  “top” edge a − b (or b − a) and the bottom edge c − d (or d − c), to get E = {{a, b} , {c, d}}. But switching the top and bottom edge also gives the same E! So there are actually ╱2(4)、/2 = 3 ways.

Alternately, there is an edge {1,b} for one of b = 1, 2, 3, and there is an edge with the other two elements, so there are 3 ways.

• Graph 4: There are 4 ways to label the isolated vertex, and then 3 choices for the upper left vertex. Label the other two vertices with the remaining numbers. So there are 12 ways.

• Graph 5: There are 4 ways to label the upper left vertex. Assign the other three vertices the remaining numbers in any order; they all give the same abstract graph. So there are 4 ways.