2
$\begingroup$

I'm working through Graph Theory by Bondy and Murty, and I'm surprised by the 9.2.3 exercise in the Connectivity chapter:

Let $C$ be a cycle of length at least three in a nonseparable graph $G$, and let $S$ be a set of three vertices of $C$. Suppose that some component $H$ of $G-V(C)$ is adjacent to all three vertices of $S$. Show that there is a 3-fan in $G$ from some vertex $x$ of $H$ to $S$.

What surprises me is that I seem to be able to reach the same conclusion with much weaker and simpler hypotheses, namely:

Let $X$ be a set of vertices in a graph $G$, and $S$ a subset of $X$ of three vertices. Suppose that some component $H$ of $G-X$ is adjacent to all three vertices of $S$. Then there is a 3-fan in $G$ from some vertex $x$ of $H$ to $S$.

Here I'm relying neither on the nonseparability of $G$ nor on the existence of a cycle.

Am I missing anything in my reasoning?


(Tentative) Proof:

Let $\{s_1, s_2, s_3\} = S$, and define $\overline H$ by extending $H$ to contain $S$ and, for each of the $s_i \in S$, one edge $e_i$ from $s_i$ to $H$.

By construction, $\overline H$ is connected, so let $P$ an $(s_1, s_2)$-path in $\overline H$. Furthermore, since $\overline H$ is connected, let $Q$ an $(s_3, V(P))$-path in $\overline H$, and denote $x$ the terminal vertex of $Q$:

3-fan diagram

$x$ divides $P$ into an $(x, s_1)$-path $P_1$ and an $(x, s_2)$ path $P_2$; what's more, it is easily verified that $x \notin S$ (since any path which ends in $s_i$ contains $e_i$), and that $P_1$, $P_2$ and $Q$ are internally disjoint.

It follows that $(P_1, P_2, Q)$ is a 3-fan from $x \in H$ to $S$. Q.E.D.

$\endgroup$
2
  • 1
    $\begingroup$ seems legit to me (except in the fist sentence of the proof, you probably meant to write "... one edge $e_i$ from $s_i$ to $H$"). $\endgroup$ May 25, 2018 at 12:22
  • $\begingroup$ @HagenvonEitzen oh right, I fixed the typo, thanks. $\endgroup$ May 25, 2018 at 12:27

0

You must log in to answer this question.

Browse other questions tagged .