Skip to content

Homework 7

  1. Prove that if a connected (undirected) finite graph has exactly \(2k\) vertices of odd degree, then the set of edges can be partitioned into \(k\) paths such that every edge is used exactly once.

    If we cut the graph into two pieces(cut one time), then each piece of graph may at most lose 2 degree respectively at the starting point and endpoint, that is, the parity of at most 2 vertices will be changed.
    Then we ignore one piece and consider all the rest piece. When we cut one time, at most 2 vertices' parities have been changed.
    Inductively
    Cutting one time| at most \(2k-2\) vertices of odd degree | 1 path
    Cutting two time| at most \(2k-2\times 2\) vertices of odd degree | 2 paths
    ...
    Cutting \(k-1\) time | at most \(2k - 2(k-1)=2\) vertices of odd degree | \(k-1\) paths
    Then if we have \(k-1\) paths we have 2 vertices of odd degree.
    Then the rest part of graph can form a Euler walk by theorem.
    That is we have \(k\) paths that every edge is used exactly once.

  2. Does there exist a graph with \(|V| \ge 2\) such that the degrees of the vertices are all different?

    Suppose \(\#V=n\), \(V=\{v_1, ..., v_n\}\). and all the degrees of vertices are all different.
    Then since we have \(n\) vertices. Then \(\deg v_{i} \le n-1\) for all \(i\). by def of graph.
    Then the set of degrees can only be \(\{0, 1, ..., n-1\}\) for \(n\) vertices.
    But if \(\exists v_i\): \(\deg v_{i} = n-1\). Then \(v_i\) must connect all the other vertices. Then all the other vertices have more than 0 degree.
    Which is contradiction to one of degree is 0. Thus there doesn't exist such graph.

  3. A graph has six edges. Is it possible that both conditions hold?

    1. there is a walk which traverses every edge exactly twice;
    2. there is no Eulerian path.

    Yes, First we consider a graph that doesn't admit a Eulerian path. Then we duplicate edges on each edge, that is if \(a\) is connected to \(b\) via edge \(1\), then we add edge \(2\) that connect \(a\) and \(b\). Then \(a\) and \(b\) is connected by two edges. Do this process for each edge
    Then is this new graph, the degree of every vertices must be even. Then there is an Eulerian path that use the edge exactly twice. Thus it is possible

    For example for \(K_4\) and vertices are \(1,2,3,4\) in order. Then there is no Euler path since the degree of each vertex is \(3\), but there is a walk satisfy condition a). Walk: 1 -> 2 -> 3 -> 1 -> 4 -> 2 -> 3 -> 4 -> 1 -> 2 -> 4 -> 3 -> 1. Thus it is possible

  4. Consider the graph \(S_n(V, E)\) where \(V\) is the set of all possible \(2^n\) subsets of \(\{1, ..., n\}\), and the vertices \(u, v \in V\) are adjacent, iff \(u \cap v = \emptyset\). Does this graph admit an Euler tour? An Euler path, which is not a tour?

    Take \(v = \{i_1, i_2, ..., i_k\} \subseteq \{1, ..., n\}\).

    If \(k=0\), that is \(v=\empty\), then \(u\) has \(2^n-1\) possibilities
    If \(k=n\), that is \(v=\{1,2,...,n\}\), then \(v\) has one possibility
    If \(0<k<n\), then consider the complement: \(\{j_1, j_2, ..., j_{n-k}\}\) where \(v \cup \{j_1, ..., j_{n-k}\} = V\)
    There are \(2^{n-k}\) subsets of \(\{j_1, ..., j_{n-k}\}\). And all these subsets \(\cap v = \emptyset\). Then there are \(2^{n-k}\) vertices adjacent to \(v\).
    Then the degree of \(v\) is \(2^{n-k}\). Generally, all the vertices of \(0<k<n\) has even degree.
    In the end, we have two vertices of odd degree and others are all even degrees
    Thus there is an Euler walk but not Euler tour.

‍