<p>Consider the graph <span class="math-container">$G = (V,E)$</span> with vertex set <span class="math-container">$V=\{a,b,c,d,x,y,z,u\}$</span> and edge set <span class="math-container">$E=\{ac,bd,au,bu,cu,du,ax,bx,cy,dz\}$</span>. Then, if I am not mistaken, <span class="math-container">$x,b,u,c,y$</span> is an induced path through <span class="math-container">$u$</span> between <span class="math-container">$x$</span> and <span class="math-container">$y$</span>, <span class="math-container">$x,a,u,d,z$</span> is an induced path through <span class="math-container">$u$</span> between <span class="math-container">$x$</span> and <span class="math-container">$z$</span>, and <span class="math-container">$y,b,u,d,z$</span> is an induced path through <span class="math-container">$u$</span> between <span class="math-container">$y$</span> and <span class="math-container">$z$</span>. However, <span class="math-container">$G$</span> is claw-free.</p>

CC BY-SA 4.0
2024-02-29T20:57:14.773Z
2024-02-29T20:57:14.773Z
NaturalLogZ
<p>Let <span class="math-container">$G$</span> be a claw-free graph, and let <span class="math-container">$x,y,z,u$</span> be distinct vertices of <span class="math-container">$G$</span>. Is the following possible in <span class="math-container">$G$</span> ?
There are three <strong>induced</strong> paths through <span class="math-container">$u$</span>: between <span class="math-container">$y$</span> and <span class="math-container">$z$</span> (i.e., <span class="math-container">$y \rightsquigarrow u \rightsquigarrow z$</span>), between <span class="math-container">$x$</span> and <span class="math-container">$z$</span> (i.e., <span class="math-container">$x \rightsquigarrow u \rightsquigarrow z$</span>), and between <span class="math-container">$x$</span> and <span class="math-container">$y$</span> (i.e., <span class="math-container">$x \rightsquigarrow u \rightsquigarrow y$</span>).</p>
<p>It seems that this is impossible in a claw-free graph...
Would appreciate any help with a refutation, or perhaps insights to a proof.</p>

<ds.algorithms><graph-theory><graph-algorithms><planar-graphs>
Question about claw-free graphs
BBK
# Question about claw-free graphs

(Asked by: username_0 on 2024-02-29)

Let $G$ be a claw-free graph, and let $x,y,z,u$ be distinct vertices of $G$. Is the following possible in $G$ ?
There are three **induced** paths through $u$: between $y$ and $z$ (i.e., $y \rightsquigarrow u \rightsquigarrow z$), between $x$ and $z$ (i.e., $x \rightsquigarrow u \rightsquigarrow z$), and between $x$ and $y$ (i.e., $x \rightsquigarrow u \rightsquigarrow y$).

It seems that this is impossible in a claw-free graph...
Would appreciate any help with a refutation, or perhaps insights to a proof.

**Tags:** ds.algorithms, graph-theory, graph-algorithms, planar-graphs


---

## 1 answers

### Answer by username_1 on 2024-02-29. Score: 1

Consider the graph $G = (V,E)$ with vertex set $V=\{a,b,c,d,x,y,z,u\}$ and edge set $E=\{ac,bd,au,bu,cu,du,ax,bx,cy,dz\}$. Then, if I am not mistaken, $x,b,u,c,y$ is an induced path through $u$ between $x$ and $y$, $x,a,u,d,z$ is an induced path through $u$ between $x$ and $z$, and $y,b,u,d,z$ is an induced path through $u$ between $y$ and $z$. However, $G$ is claw-free.


---

