Let $G$ be a graph which does not contain a simple cycle $v_1\ldots v_k$ and two "crossing" chords $v_iv_j$ and $v_pv_q$, $i<p<j<q$. An example of such graph is a triangulation of the convex polygon. Is it true that the number of edges in $G$ does not exceed $2n-3$, where $n$ denotes the number of vertices?
$\begingroup$
$\endgroup$
4
asked Nov 15, 2020 at 16:25
-
$\begingroup$ Isn't such a graph automatically outerplanar? $\endgroup$– Martin RubeyCommented Nov 15, 2020 at 17:10
-
$\begingroup$ @MartinRubey it may be even not planar (take a subdivision of $K_5$) $\endgroup$– Fedor PetrovCommented Nov 15, 2020 at 17:15
-
$\begingroup$ Cool, thanks. $K_{2,3}$ is another example. $\endgroup$– Martin RubeyCommented Nov 15, 2020 at 17:18
-
$\begingroup$ If the graph is Hamiltonian and has this property, then it is outerplanar. $\endgroup$– David WoodCommented Nov 15, 2020 at 21:40
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
Thomassen and Toft [JCTB 31(2):199-224, 1981] showed that any graph with minimum degree at least 3 contains a cycle with two crossing chords from neighbouring vertices on the cycle. The $2n-3$ upper bound follows by induction on $n$, since we may delete a vertex of degree at most $2$.
$\begingroup$
$\endgroup$
2
Assume $n=2k+2$ is even. Let $G$ be the graph obtained from a matching $v_1w_1,\dots,v_kw_k$ by adding two vertices $x$ and $y$ both adjacent to all of $v_1,w_1,\dots,v_k,w_k$. So $G$ has $n$ vertices and $5k=\frac{5}{2}(n-2)$ edges. Consider a cycle $C$ in $G$. If $|C|=3$ then $C$ has no chords. Otherwise $|C|=4$ and both $x$ and $y$ are in $C$. If $C=(x,v_i,y,w_i)$ for some $i\in\{1,\dots,k\}$, then $C$ has only one chord (namely $v_iw_i$). Otherwise $C$ has no chords. So $G$ satisfies a stronger property (every cycle has at most one chord).
-
$\begingroup$ Cycles $(x, v_i, w_i, y, v_j, w_j)$ have crossing chords $xw_i$ and $y v_i$. $\endgroup$ Commented Nov 15, 2020 at 23:54
-
1$\begingroup$ Good point. My example says nothing! $\endgroup$ Commented Nov 15, 2020 at 23:59