Find the smallest positive constant $c$ satisfying: For any simple graph $G=G(V,E)$, if $|E|\geq c|V|$, then $G$ contains $2$ cycles with no common vertex, and one of them contains a chord. Note: The cycle of graph $G(V,E)$ is a set of distinct vertices ${v_1,v_2...,v_n}\subseteq V$, $v_iv_{i+1}\in E$ for all $1\leq i\leq n$ $(n\geq 3, v_{n+1}=v_1)$; a cycle containing a chord is the cycle ${v_1,v_2...,v_n}$, such that there exist $i,j, 1< i-j< n-1$, satisfying $v_iv_j\in E$.
Problem
Source: 2014 China TST 2 Day 2 Q5
Tags: combinatorics proposed, combinatorics, graph theory
31.12.2014 08:57
Anybody ideas for this hard problem?
28.03.2015 06:11
Here's a solution, though I would call it pretty ugly. Not sure why I spent so much time on this problem... I claim the answer is $c = 4.$ A construction is taking a $K_{4, n}$ for large positive integers $n$. This graph can have at most 2 disjoint cycles, since each cycle needs two vertices on the side with 4 vertices. Also, that implies the length of both is 4, and that they have no chord. This gives $4n$ edges for $n+4$ vertices. So clearly we need at least $c \ge 4$. The rest is showing that $c = 4$ works. We proceed by induction. Base cases are easy to verify. If a vertex has degree $\le 4$, we can remove it from our graph and induct on the remaining graph. Therefore, we assume that all vertices have degree at least 5. We do what is "most obvious" (I guess that maybe it isn't all that obvious that this works...) : take the longest path in the graph. Let the path be from $A = v_0, v_1, v_2, \dots, v_k = B$. We do 2 cases: Case 1: $AB$ is not an edge. Proof: Since the path is maximal, $A$ has 4 neighbors among the points $v_1, v_2, \dots, v_{k-1}$, as does $B$. I claim that this is enough to get a disjoint cycle and chorded cycle. Let the 4 neighbors of $A$ be $v_{a_1}, v_{a_2}, v_{a_3}, v_{a_4}$ and the 4 neighbors of $B$ be $v_{b_1}, v_{b_2}, v_{b_3}, v_{b_4}$, where $a_1 < a_2 < a_3 < a_4$ and $b_1 < b_2 < b_3 < b_4$. Now sort these 8 vertices (the 4 from $A$ and $B$) in increasing order. Note that you can get vertices that coincide. If $a_1$ is the first or second smallest after sorting (then clearly $a_1 < b_3 < b_4$), then we can take the cycle $A = v_0, v_1, v_2, \dots, v_{a_1}, v_0 = A$ and the chorded cycle $B = v_k, v_{k-1}, \dots, v_{b_3}, v_k$ with the chord $v_kv_{b_4}$. Otherwise, $a_1$ is not first or second smallest, so $b_1 < b_2 < a_1 < a_2 < a_3.$ Now take the cycle $B = v_k, v_{b_2}, v_{b_2-1}, \dots, v_{b_1}, v_k = B$ and the chorded cycle $A = v_0, v_{a_1}, v_{a_1+1}, \dots, v_{a_3}, v_0 = A$, with chord $v_0v_{a_2}.$ So this case is done. Case 2: $AB$ is an edge. Proof: This case is actually rather easy because now $A = v_0, v_1, \dots, v_k = B, v_0 = A$ is a cycle. In particular, all neighbors of vertices in this cycle must be other vertices in this cycle, because the path chosen was maximal. Assume for contradiction that we cannot find both a chorded cycle and a cycle. Now I prove the following easy claim: $\deg v_i + \deg v_{i+1} \le 13.$ (indices $\pmod{k+1}$ of course) To do this, we essentially treat $v_i$ as $A$ and $v_{i+1}$ as $B$ (you can do this because it is a cycle) Of course it suffices to prove this claim for the case $v_0$ and $v_k$. (everything is symmetric, due to cycle) Let $A = v_0$ and $B = v_k$, and let the path be $A = v_0, v_1, \dots, v_k = B$. If $\deg A \ge 6$ and $\deg B \ge 6$, then we're done by the same argument as Case 1 (both $A$ and $B$ would have 4 neighbors among $v_1, v_2, \dots, v_{k-1}.$ The reason we only get $4$ neighbors instead of $5$ is because $AB$ is an edge) So now assume that $\deg A = 5$, and let the neighbors of $A$ be $v_{a_1}, v_{a_2}, v_{a_3}$ where $0 < a_1 < a_2 < a_3 < k$. If $B$ has any neighbors in the range $v_{a_3+1}, v_{a_3+2}, \dots, v_{k-2},$ then we use that vertex and $B$ to create a cycle. Then use $A = v_0, v_1, \dots, v_{a_2}, v_0 = A$ to create a chorded cycle with chord $v_0v_{a_1}.$ In $B$ has at least 2 neighbors in the range $v_{a_2+1}, v_{a_2+2}, \dots, v_{a_3-1},$ let them be $v_{b_1}, v_{b_2}$. We create a cycle using $v_0 = A$ and $v_{a_1}$ while creating a chorded cycle using $B, v_{b_1}, v_{b_2}.$ If $B$ has 3 neighbors in the range $v_1, v_2, \dots, v_{a_1-1}$, then call them $v_{b_3}, v_{b_4}, v_{b_5}$. Use these 3 vertices along with $B$ to create a chorded cycle, and use $A = v_0, v_{a_1}, v_{a_2}$ to create another cycle. Since we are operating under contradiciton, in those ranges $B$ has at most $0, 1, 2$ neighbors respectively. What other neighbors can $B$ have? The only other possibilities are $v_0 = A, v_{k-1}, v_{a_1}, v_{a_2}, v_{a_3}$, so $5$ more. In total $B$ has degree at most $0+1+2+5 = 8$. Since $\deg A = 5$, $\deg A + \deg B \le 13.$ Now sum \[ \sum_{i = 0}^{k} (\deg v_i + \deg v_{i+1}) \le 13(k+1) \implies \sum_{i = 0}^k \deg v_i \le \frac{13k}{2} \implies |E| \le \frac{13k}{4} < 4|V|, \] a contradiction. Therefore, this case is also finished, so we're done.
08.06.2015 10:39
Up to Case 1 it is quite a nice and natural argument. It only turns a bit ugly because of the annoying Case 2. I initially had a similar Case 2 with sum of degrees 14 instead of 13. I didn't check in detail the argument above to see if I could get away with 13 or whether there is some mistake and 14 is needed. I do have a nicer ending though: If $AB$ is an edge then we may assume that the chosen maximal path $P$ contains all the vertices. Indeed the maximality of the path and the fact that we can close it to a cycle shows that there is no edge between $P$ and $V \setminus P$. But one of the graphs $G[V]$ and $G[V\setminus P]$ satisfies the induction hypothesis and so it contains a cycle and a chorded cycle. Now pick any vertex $v_1$ of degree at least $6$ and a Hamilton path starting at $v_1$. (Possible as we have a Hamilton cycle.) Say the Hamilton path is $v_1v_2\cdots v_n$ and (some of) the neighbours of $v_1$ are $v_2,v_a,v_b,v_c,v_d,v_n$ where $2 < a < b < c < d< n$. (If $v_n$ is not a neighbour, then we are done by Case 1.) If $v_n$ is not a neighbour of $v_{a-1}$ then we can consider the Hamilton path $v_{a-1}v_{a_2}\cdots v_1v_av_{a+1}v_{a+2}\cdots v_n$ and end up in Case 1. So we may assume that $v_n$ is adjacent to $v_{a-1}$ and by similar considerations to $v_{b-1},v_{c-1}$ and $v_{d-1}$ as well. So $v_n$ also has degree at least $6$. But now we can remove the edge $v_1v_n$ and finish by the same argument as in Case 1.