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 \[C*C'=\{x|x\in (C-C')\cup (C'-C)\}.\](1) Let $r$ be the largest postive integer so that we can choose $r$ cycles $C_1,C_2,\ldots,C_r$ and for all $1\leq k\leq r$ and $1\leq i$, $j_1,j_2,\ldots,j_k\leq r$, we have \[C_i\neq C_{j_1}*C_{j_2}*\cdots*C_{j_k}.\](Remark: There should have been an extra condition that either $j_1\neq i$ or $k\neq 1$) (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 $\{A_iA_{i+1},1\leq i\leq n\}$ where $n\geq 3$, $A_1,A_2,\ldots,A_n$ are distinct vertices, and $A_{n+1}=A_1$.