Problem

Source: 2018 Taiwan TST Round 3

Tags: linear algebra, combinatorics, Taiwan



Given a connected graph with n edges, where there are no parallel edges. For any two cycles C,C in the graph, define its outer cycle to be CC={x|x(CC)(CC)}.(1) Let r be the largest postive integer so that we can choose r cycles C1,C2,,Cr and for all 1kr and 1i, j1,j2,,jkr, we have CiCj1Cj2Cjk.(Remark: There should have been an extra condition that either j1i or k1) (2) Let s be the largest positive integer so that we can choose s edges that do not form a cycle. (Remark: A more precise way of saying this is that any nonempty subset of these s edges does not form a cycle) Show that r+s=n. Note: A cycle is a set of edges of the form {AiAi+1,1in} where n3, A1,A2,,An are distinct vertices, and An+1=A1.