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∈(C−C′)∪(C′−C)}.(1) Let r be the largest postive integer so that we can choose r cycles C1,C2,…,Cr and for all 1≤k≤r and 1≤i, j1,j2,…,jk≤r, we have Ci≠Cj1∗Cj2∗⋯∗Cjk.(Remark: There should have been an extra condition that either j1≠i or k≠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 {AiAi+1,1≤i≤n} where n≥3, A1,A2,…,An are distinct vertices, and An+1=A1.
Problem
Source: 2018 Taiwan TST Round 3
Tags: linear algebra, combinatorics, Taiwan
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 e1,⋯,en−s, and denote the corresponding cycle D1,⋯,Dn−s, clearly D1,⋯,Dn−s satisfy the condition in (1), since Di is the only cycle to contain edge ei, for all 1≤i≤n−s. This shows that r≥n−s. Thus we are left to prove r≤n−s. Note that ∗ operation is the well-known "symmetric difference", but if we work in F2, 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 D1,⋯,Dn−s. If this is proved, then D1,⋯,Dn−s is a basis of the vector space of cycles, hence r≤n−s. Pick any cycle C in the graph, it must contain some blue edges, WLOG blue edges are e1,⋯,ek, and are arranged on the cycle in this order. Fix a vertice v in the tree T. We can write Di as Xi+Yi+ei (note that we are working in F2) uniquely, where Xi are edges travelling from an endpoint of ei to v, Yi are edges travelling from the other endpoint of ei to v, and Xi,Yi⊆T. Thus k∑i=1Di=k∑i=1(Xi+Yi+ei)=k∑i=1(ei+Yi+Xi+1)In the last expression, Yi+Xi+1 consists of edges from ei to v and v to ei+1, so it's the unique road connecting ei and ei+1, which is exactly the red edges between ei and ei+1 in the given cycle C. So ∑ki=1Di=C. We are done!