PUMaC 2019 · 个人决赛（B 组） · 第 2 题

PUMaC 2019 — Individual Finals (Division B) — Problem 2

Let G = ( V, E ) be a simple connected graph. Show that there exists a subset of edges F ⊆ E such that every vertex in H = ( V, F ) has odd degree if and only if | V | is even. Note: A connected graph is a graph such that any two vertices have a sequence of edges connecting one to the other. Note: A simple graph has no loops (edges of the form ( v, v )) or duplicate edges.

解析

Let G = ( V, E ) be a connected graph. Show that there exists a subset F ⊆ E such that every vertex in H = ( V, F ) has odd degree if and only if | V | is even. Note: A connected graph is a graph such that for any two vertices there is a path from one to the other. Solution : Suppose first that | V | is even and proceed by induction. Suppose the contrary, that there is no such F . Then take a spanning tree of G . By the assumption, this spanning tree does not have all the vertices with odd degree, so there exists a vertex v with even degree. Now make v the root of the spanning tree. Then one of the subtrees of v has an odd number of vertices, because the total number of vertices is even. Let the vertex in that subtree which is a child of v be u . Then u has an even number of children, call this set V . Let V be the 1 2 set of all the other children of v except u and V . Then apply the inductive hypothesis to 1 the induced graphs on V and V , and suppose we get sets F and F of edges. Then the set 1 2 1 2 F ∪ F ∪ { uv } satisfies the desired property. 1 2 Now if the graph G satisfies this property, then we can apply the usual double counting formula ∑ for the subgraph of G with edges F to get that d ( v ) = 2 | F | , where d ( v ) denotes the F F v ∈ V degree of v in the graph on V with edges F . Then each d ( v ) is odd by assumption, so | V | is F even. Proposed by Bill Huang. Solution by Aleksa Milojevi´ c.