PUMaC 2013 · 个人决赛（A 组） · 第 3 题
PUMaC 2013 — Individual Finals (Division A) — Problem 3
题目详情
- A graph consists of a set of vertices, some of which are connected by (undirected) edges. A star of a graph is a set of edges with a common endpoint. A matching of a graph is a set of edges such that no two have a common endpoint. Show that if the number of edges of a graph 2 G is larger than 2( k − 1) , then G contains a matching of size k or a star of size k . 1
解析
- A graph consists of a set of vertices, some of which are connected by (undirected) edges. A star of a graph is a set of edges with a common endpoint. A matching of a graph is a set of edges such that no two have a common endpoint. Show that if the number of edges of a graph 2 G is larger than 2( k 1) , then G contains a matching of size k or a star of size k . Solution First, assume that there is no star of size k , as if there is, then we are trivially done. Then, for any arbitrary edge AB , we know that both vertices A and B have at most k 1 edges, or k 2 other edges. Hence, there are at most 2 k 4 adjacent edges. Now, any edge that is not AB and is not one of the at most 2 k 4 adjacent edges has no endpoint in common with AB , so they satisfy the conditions of a matching. Then, consider the following operation - choose any arbitrary edge A B , and remove it and 1 1 the at most 2 k 4 adjacent edges from the graph. Repeat this operation on the graph, that is, on the new graph with at most 2 k 3 less edges, choose another arbitrary edge A B and remove it and its adjacent edges from the graph. 2 2 Then, any edge left in the graph satisfies the conditions of a matching with both A B and 1 1 A B . 2 2 2 Repeat this operation k 1 times, as | E ( G ) | > 2( k 1) > ( k 1)(2 k 3). Then, A B for i i i = 1 , · · · , k 1 satisfy the conditions of a matching, as does any edge still left in the graph, which much exist as we have removed at most ( k 1)(2 k 3) edges. Therefore, we found k edges that satisfy the conditions of a matching, so a matching exists. 2