# CS 163/265, Fall 2022, Homework 4

Due Friday, November 4, in Gradescope.

1. Find a graph that has an Euler tour (it is connected and all degrees are even) in which there exists a path $$uvw$$ whose edges cannot be used consecutively as part of an Euler tour. (Hint: If it appears consecutively, it can appear at the start of the tour. Use Fleury's algorithm to show that, in your graph, using this path at the start of a tour would be a mistake.)

2. Let $$S$$ be a set of integers, represented as a binary number as in the course lecture notes. Suppose we want to construct the set $$T$$ of integers $$i$$ for which both $$i$$ and $$i+1$$ belong to $$S$$. For instance, when $$S=\{1,2,3,6,8,9\}$$, we should construct $$T=\{1,2,8\}$$. Write the simplest expression you can find for $$T$$. Use programming notation, not mathematical set notation.

3. Define the width of a walk (just like the width of a path) to be the minimum weight of any of its edges. Define a "widest traveling salesperson tour" to be a walk through a graph, starting and ending at the same vertex and visiting every vertex, that has the largest possible width.

1. 163 students only: For the four-vertex graph used as an example for the exact TSP algorithm, find a widest traveling salesperson tour. (Hint: Remember that walks are allowed to repeat vertices. The optimal solution is not one of the three tours used in the example.)

2. 265 students only: Describe a polynomial-time algorithm for finding the widest traveling salesperson tour. (Hint: it is the same as one of the other TSP-related algorithms we studied.)

4. In the $$G(n,\tfrac12)$$ model of random graphs, every graph on a given set of $$n$$ vertices is equally likely, and therefore every graph is possible. Find a graph with four vertices that cannot be generated by the Barabasi–Albert model, no matter what parameter $$d$$ is used.