Skip to content

5.7 Euler Tour

  1. 100 circles are drawn on the plane form a connected figure. Can you draw this figure without ever lifting the pencil and not going along the same line twice?

    Use induction to prove the degree are even no matter two circles have one intersection point or two intersection points

    First, consider two circleimage, then easily.....

  2. You have a wire of length 10. You want to construct a pentagonal pyramid with every edge being 1. Can you do it without cutting the wire? If not, how many cuts are enough?

    We cannot do it without cutting the wire since all the degrees of vertices are odd

    If we cut the wire into two pieces, then each piece of wire may at most loose 2 degree respectively at the endpoints, that is, the parity(奇偶性) of two vertices may be changed

    Maybe less, since it can form a circle

    Then two pieces of wire can change at most 4 vertices' parties

    Then we can form a Euler walk when reduce these two pieces of wire.

    In the end, we need three wires

    image​

    image​

    Yes, it is enough to cut 2 times

  3. Can a cat walk around the yard, crossing every fence exactly once? A fence is any segment bounded by two bold points.

    image​

    ​​image​

    No, since there are more than 2 vertices of odd degree

  4. De Bruijn graph of order \(l\) for size \(k\) alphabet \(A\) is the directed graph defined as follows

    • The vertex set is the set of all possible words of length \(l\) in \(A\);
    • Every vertex \(v = w_1...w_l\) have exactly \(k\) outgoing edges to vertices \(w_2w_3...w_lb\), where \(b \in A\);
    • Additionaly, the edges between \(w_1...w_l\) and \(w_2w_3...w_lb\) is marked by \(b\).

  5. Draw de Bruijn graphs for \(k=2, l=2,3\).

    image​

    image​

  6. Show, that a connected directed graph admits an Eulerian tour that follows the directions of edges if and only an in-degree of every vertex coincides with the corresponding out-degree.

  7. Show, that every de Bruijn graph admits an Eulerian tour.

    image​

  8. Show, that there exist a string of length \(k^{l+1}+l\) of letters of \(A\), such that this string contains all possible words of length \(l+1\).

    image​

    image​

‍