A graph is called a self-intersecting graph if it is isomorphic to a graph whose every edge is a segment and every two edges intersect. Notice that no edge contains a vertex except its two endings. a) Find all $ n$'s for which the cycle of length $ n$ is self-intersecting. b) Prove that in a self-intersecting graph $ |E(G)|\leq|V(G)|$. c) Find all self-intersecting graphs.
Problem
Source: Iranian National Olympiad (3rd Round) 2008
Tags: combinatorics proposed, combinatorics
mavropnevma
14.11.2011 11:44
To my knowledge, Conway's thrackle conjecture is still open, thus points b) and c) are moot. The link states that all cycles $C_n$, except for $n=4$, have thrackle embeddings.
Octav
14.11.2011 21:31
mavropnevma wrote: To my knowledge, Conway's thrackle conjecture is still open, thus points b) and c) are moot. The link states that all cycles $C_n$, except for $n=4$, have thrackle embeddings. The problem stated here asks for the graph to have each edge straight; or, as far as I understood, Conway's thrackle conjecture deals with Jordan arcs, which are a broad generalization of segments. For example, I think the answer to point a) is that $C_n$ is self-intersecting only for odd $n$'s. The example is classical: take the regular $n$-gon and the cycle formed by its big diagonals. For even $n$, suppose that $C_n$ is self-intersecting, put an edge $AB$ vertically in plane, and denote its two "sides" (the regions of the plane which it delimits) by the "left side" and the "right side". Suppose WLOG that $A$ is connected to a vertex $C$ on the left side. Since any two edges cross each other, we know that the next point in the cycle that is connected to $C$ will be on the right side, and so on. By the parity of $n$, we know that the last point $D$ in the cycle will be on the right side of the edge $AB$. But then $BD$ is an edge, and so is $AC$, and they are completely included in different sides of the plane, thus they do not intersect, a contradiction.
mavropnevma
14.11.2011 21:41
Right so - it escaped my noticing the edges must be segments. In that case point b) is solved, via a nice proof by Perles; see http://www.cims.nyu.edu/~pach/publications/monotonethrackle110209.pdf for the proof (Theorem 1). The theorem is attributed to Hopf and Pannwitz, in a slightly different setting. c) It seems like Woodall characterized all such graphs, called geometric (or straight-line) thrackles, but his paper is unavailable to me.
Math4tots
14.11.2011 23:22
My solution to part b)
Let $v$ be a vertex, $E_v$ be the set of edges that share the vertex $v$, and $u_e$ be the endpoint of $e$ that is not $v$.
Suppose $|E_v| \ge 3$. Let $e \in E_v$. If we extend $e$ to a line, we may partition $E_v - {e}$ into sets $A_e$ and $B_e$ depending on which side of the line each edge extends to. It is clear that for all but up to two choices of $e$, the sets $A_e$ and $B_e$ must be non-empty. Notice that if we draw an edge that starts from $u_e$ and crosses an edge in $A_e$, it cannot cross any edges in $B_e$. It follows that $e$ is the only segment that crosses $u_e$ when both $A_e$ and $B_e$ are non-empty. It follows that deleting the edge $e$ and the vertex $u_e$ in this case does not affect that value $|V(G)| - |E(G)|$. So for the purposes of this problem, we may instead consider the graph $G - {u_e}$. In fact, through repeated application, we see that we only need to consider graphs in which each vertex is crossed by at most two edges.
If each vertex is crossed by at most two edges, we have $\sum |E_v| \le 2 * |V(G)|$, and since in the sum each edge is counted twice (once for each endpoint), $|E(G)| = \frac{\sum|E_v|}{2} \le |V(G)|$.
Pathological
13.11.2019 03:29
For part a), the answer is all odds. For odds, we can just take stars. For evens, consider the number of times any given one of its segments is crossed. This number must be even clearly, but it is also $n-3$, contradiction. We will show that all connected self-intersecting graphs with a cycle must have exactly one cycle. This would clearly solve b) by considering each connected component separately. So let's show this. First of all, we know that the cycle must be odd. It's also readily seen that the cycle must be a star, where the sum of the "angles" of the cycle is $\pi.$ Now, we claim that any other edge of the graph must have at least one endpoint among the vertices of the cycle. If not, then consider the angle of the cycle which contains the direction of the edge, and notice that this edge can't intersect both of the two edges spanning the angle. Finally, we will show that all vertices of the graph which aren't on the cycle are leaves. This would imply the claim, and solve part b). If not, then there would be some vertex not in the cycle which is connected to two vertices of the cycle. This means that the vertex must be contained in the angles subtended by the edges adjacent to those to vertices. From here, it's easy to find a contradiction, as the intersection of those two angles is contained within the "star." $\square$