chords in a cycle at graph theory

488 Views Asked by At

$G=(V,E)$ is undirected graph which follow the rule $\delta(G)\ge3 $ I need to show that it has inside at least one cycle $C$ with at least one chord ($(x,y)$ is a chord of $C$ if $x$,$y$ are indeed at $C$ but edge $(x,y)$ arent inside.) any directions what can i do?

1

There are 1 best solutions below

0
On BEST ANSWER

Let $P$ be a maximal path in $G$, $v$ an endpoint of $P$. Since $v$ has degree at least 3, 2 edges starting at $v$ (different from the edge of $P$ ending in $v$) have their other endpoint on $P$.

This exhibits a cycle and a chord in that cycle.