PUMaC 2019 · 个人决赛（A 组） · 第 1 题

PUMaC 2019 — Individual Finals (Division A) — Problem 1

Given the graph G and cycle C in it, we can perform the following operation: add another vertex v to the graph, connect it to all vertices in C and erase all the edges from C . Prove that we cannot perform the operation indefinitely on a given graph. m − 1

解析

Given the graph G and cycle C in it, we can perform the following operation: add another vertex v to the graph, connect it to all vertices in C and erase all the edges from C . Prove that we cannot perform the operation indefinitely on a given graph. Solution : The number of edges stays constant, the graph stays connected, the number of vertices increases: at some point, we will have | E | + 1 = | V | . Then, our graph is a tree without cycles. The process stops then. m − 1