AoPS - Problem

Source: 2018 Taiwan TST Round 3

Tags: linear algebra, combinatorics, Taiwan

USJL

02.04.2020 10:10

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$ .

Rickyminer

21.06.2020 17:13

This is indeed purely linear algebra Consider any fixed choice of $s$ edges in (2). For simplicity, let's color the $s$ edges red, and color the remaining $n-s$ edges blue. Since $s$ is the largest integer to satisfy the condition, hence that Red edges form a tree, say $T$ . It's because red edges doesn't form a cycle, but added any edges to it will form a cycle. For any fixed blue edge, there exists exactly one cycle, which is formed by the blue edge and some of red edges. If we label the blue edges $e_1,\cdots,e_{n-s},$ and denote the corresponding cycle $D_1,\cdots,D_{n-s},$ clearly $D_1,\cdots,D_{n-s}$ satisfy the condition in (1), since $D_i$ is the only cycle to contain edge $e_i,$ for all $1 \le i \le n-s$ . This shows that $r \ge n-s$ . Thus we are left to prove $r \le n-s$ . Note that $*$ operation is the well-known "symmetric difference", but if we work in $\mathbb{F}_2,$ it can be simply viewed as $+$ . So the condition in (1) can be reworded as following: none of the cycles can be represented as a linear combination of other cycles. We are going to prove that any cycles in the graph can be represented as a linear combination of $D_1,\cdots,D_{n-s}.$ If this is proved, then $D_1,\cdots,D_{n-s}$ is a basis of the vector space of cycles, hence $r \le n-s$ . Pick any cycle $C$ in the graph, it must contain some blue edges, WLOG blue edges are $e_1,\cdots,e_k$ , and are arranged on the cycle in this order. Fix a vertice $v$ in the tree $T$ . We can write $D_i$ as $X_i+Y_i+e_i$ (note that we are working in $\mathbb{F}_2$ ) uniquely, where $X_i$ are edges travelling from an endpoint of $e_i$ to $v,$ $Y_i$ are edges travelling from the other endpoint of $e_i$ to $v,$ and $X_i,Y_i \subseteq T.$ Thus $\sum_{i=1}^{k} D_i=\sum_{i=1}^{k} (X_i+Y_i+e_i)=\sum_{i=1}^{k} (e_i+Y_i+X_{i+1})$ In the last expression, $Y_i+X_{i+1}$ consists of edges from $e_i$ to $v$ and $v$ to $e_{i+1}$ , so it's the unique road connecting $e_i$ and $e_{i+1},$ which is exactly the red edges between $e_i$ and $e_{i+1}$ in the given cycle $C$ . So $\sum_{i=1}^{k} D_i=C$ . We are done!