2
$\begingroup$

The solution goes here and i have doubts in many points-:

We use induction on the sum $l$ of the lengths of the two paths, for all vertex pairs simultaneously.

If $P$ and $Q$ are $u$ $v$ paths, then $l \geq 2$.

If $l =2$, then we have distinct edges consisting of $u$ and $v$, and together they form a cycle of length $2$.

enter image description here

Here $AB$ and $CD$ are cycle Am i getting it right?

For the induction step, suppose $l \gt 2$.

If P and Q have no common internal vertices, then their union is a cycle. (same as above figure)!!

Am i right there ?

Not getting from here **If $P$ and $Q$ have a common internal vertex $w$, then let $P^{'}$ $P^{''}$ be the $uw$ subpath of $P$ and the $wv$ subpath of $P$. Similarly define $Q^{'}$ $Q^{''}$

Then $P^{'}$ $Q^{'}$ are $uw$ paths with total length less than $l$.Similarly, $P^{''}$ $Q^{''}$ are $wv$ paths with total length less than $l$. Since $P$ $Q$ are distinct, we must have $P^{'}$ $Q^{'}$ distinct or $P^{''}$ $Q^{''}$ distinct. We can apply the induction hypothesis to the pair that is a pair of distinct paths joining the same end points. This pair contains the edges of a cycle, by the induction hypothesis, which in turn is contained in the union of $P$ and $Q$ **

Please help me out !!

$\endgroup$
2
$\begingroup$

The main problem here is that your picture is wrong. Below I’ve drawn two pictures that I’ll use to try to explain the argument.

Two schematics of graphs.

The top one shows the situation when $\ell=2$: there are two edges between $u$ and $v$, and between them they make a loop. In this case the graph cannot be simple: assuming that $u\ne v$, this is the only way for the sum of the lengths of $P$ and $Q$ to be $2$.

Now we consider the case $\ell>2$. The induction hypothesis is that if there are distinct paths between two vertices $x$ and $y$ such that the sum of the lengths of these paths is less than $\ell$, then the union of the edge sets of these paths contains a cycle. As in the base case, we assume that we have distinct vertices $u$ and $v$ and distinct paths $P$ and $Q$ from $u$ to $v$, and we assume that the sum of the lengths of these paths is $\ell$.

If $P$ and $Q$ actually have no vertices in common besides $u$ and $v$, we can use the top picture as a schematic. Instead of showing the actual relevant part of the graph, it shows a sort of outline of the relevant part: the upper and lower arcs of the oval represent the paths $P$ and $Q$ without showing any of their internal detail, and of course $P$ followed by the reversal of $Q$ forms a cycle containing $u$ and $v$.

If $P$ and $Q$ do have at least one internal vertex in common, we use the bottom picture. It’s also a schematic, not (part of) the actual graph. It shows the vertices $u$ and $v$. The upper halves of the two ovals together with the straight line segment represent the path $P$ from $u$ to $v$, and the lower halves of the ovals together with the straight line segment represent the path $Q$ from $u$ to $v$. As I’ve drawn it, the two paths $P$ and $Q$ have some vertices in common besides $u$ and $v$: the unnamed vertex between the two ovals, the vertex $w$, and all vertices along the path represented by the straight line segment. This is of course just one of many possibilities, but it’s general enough to show the main ideas.

The schematic shows an internal vertex, $w$, at which the paths $P$ and $Q$ meet. (It also shows some others, but we’ll focus on $w$.) $P'$ is the part of $P$ between $u$ and $w$; in this picture it’s represented by the upper arcs of the two ovals. $Q'$ is the part of $Q$ between $u$ and $w$; in this picture it’s represented by the lower arcs of the two ovals. $P''$ is the part of $P$ between $w$ and $v$, and $Q'$ is the part of $Q$ between $w$ and $v$; in this example they happen to be the same path, though in general, of course, they need not be the same.

If $P'$ and $Q'$ were the same path from $u$ to $w$, and $P''$ and $Q''$ were the same path from $w$ to $v$, then $P$ and $Q$ would be the same path. By hypothesis $P$ and $Q$ are not the same path, so either $P'\ne Q'$, or $P''\ne Q''$ (or both). I’ve shown a case in which $P''=Q''$, so of course I have to have $P'\ne Q'$. $P'$ and $Q'$ are therefore different paths from $u$ to $w$. The sum of their lengths is certainly less than $\ell$, because $P'$ and $Q'$ between them must contain at least one edge: otherwise $P'$ would be equal to $P$ and $Q'$ to $Q$, and $w$ would be equal to $v$, contradicting our choice of $w$ as an internal vertex of $P$ and $Q$.

The induction hypothesis therefore tells us that the union of the edge sets of $P'$ and $Q'$ contains a cycle $C$. The edge set of $P'$ is contained in the edge set of $P$, and the edge set of $Q'$ is contained in that of $Q$, so $C$ is also contained in the union of the edge sets of $P$ and $Q$.

In every case, then, the union of the edge sets of $P$ and $Q$ contains a cycle, and the induction step is complete.

$\endgroup$
14
  • $\begingroup$ @:Brian in the figure where is $P$ and $Q$ ? $\endgroup$ – virat Nov 15 '16 at 9:28
  • 1
    $\begingroup$ @sourav: $P$ is the top path from $u$ to $v$, and $Q$ is the bottom path. In the lower figure $P$ is the union of $P'$ and $P''$, and $Q$ is the union of $Q'$ and $Q''$. $\endgroup$ – Brian M. Scott Nov 15 '16 at 16:13
  • 1
    $\begingroup$ @sourav: That’s the induction hypothesis. The proof is by complete induction on $\ell$. The base case is $\ell=2$. For the induction step you take $\ell>2$, assume as an induction hypothesis that the result is true for all smaller values, and use that to show that it’s true for $\ell$ as well. $\endgroup$ – Brian M. Scott Nov 15 '16 at 17:32
  • 1
    $\begingroup$ @sourav: You’re welcome! $\endgroup$ – Brian M. Scott Nov 15 '16 at 17:53
  • 1
    $\begingroup$ @sourav: The walks $uv$ and $uvuv$ are distinct, but the union of their edge sets contains just the one edge $\{u,v\}$, so it doesn’t contain a cycle. $\endgroup$ – Brian M. Scott Nov 15 '16 at 19:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.