4
$\begingroup$

Given a simple connected undirected graph. with V vertices and E edges.
Let e be some edge from E.

If I perform |V| different BFS runs - meaning started each time from a different vertex - and in every run e is part of the Spanning tree produced from the run.
Can it be belonging to some cycle?

The multiple answers I have to choose from are:

  1. it does not belong to any cycle
  2. e might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.
  3. e might belong to a cycle but if it belongs to an even-length cycle, then it must belong to an odd-length cycle.
  4. None of the above.

My claim is, because BFS is deterministic and because we performed |V| BFS on the graph, each time from a different vertex. if e was on some cycle, and it doesn't matter even-length or odd length, one of the vertices on the cycle would have caught up with it and remove it.

The only way that it belongs to every Spanning tree, is if it's un replaceable, meaning it's the only thing connecting two vertices.

Am I right? is there any formal proof th

$\endgroup$
  • $\begingroup$ BFS is not deterministic. It relies on an ordering of the neighbors of a vertex. $\endgroup$ – Yuval Filmus Oct 9 at 13:19
  • $\begingroup$ The fact that it relies on the order of the neighbors doesn't say it's not deterministic. The pseudo code for BFS is to collect it's neighbors by some order, place them in a queue and then go to the next neighbor in the queue. Noting in the implementation suggest that if you run the code multiple times on the same graph, that you will not get the same result. $\endgroup$ – ohad edelstain Oct 9 at 14:41
  • $\begingroup$ It might be difficult to analyze BFS unless you say more about how this step is implemented. Or, it might not depend on this nondeterministic choice. $\endgroup$ – Yuval Filmus Oct 9 at 15:01
  • $\begingroup$ Not sure I follow, I am referring to the standard implementation of BFS en.wikipedia.org/wiki/Breadth-first_search. $\endgroup$ – ohad edelstain Oct 9 at 15:29
  • 1
    $\begingroup$ BFS enqueues all unvisited neighbors of the current node. The algorithm doesn't specify an order. This is the "nondeterministic" part of BFS. There are many different runs of BFS, which differ both in the starting vertex and in the ordering of neighbors. $\endgroup$ – Yuval Filmus Oct 9 at 15:31
3
$\begingroup$

Let's show first that such an edge might belong to a cycle, by considering the case of a square $ab,bc,cd,da$. We will show that $ab$ could belong to BFS trees starting at arbitrary vertices. This is clear if BFS is started from $a$ or from $b$. If BFS is started from $c$, it could enqueue $a,d$ in this order; dequeue $a$; then enqueue $b$. Similarly, if BFS is started from $d$, it could enqueue $b,c$ in this order; dequeue $b$; then enqueue $a$.

In contrast, if an edge $e=(x,y)$ only belongs to odd cycles, then it cannot belong to all BFS trees. Indeed, take a shortest cycle containing $e$, and let $z$ be the vertex opposite $e$. If we start BFS from $z$, then $x,y$ are both enqueued before any of them is dequeued, since $d(z,x) = d(z,y)$ (try it on a triangle).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I get it now, ok I am convinced. $\endgroup$ – ohad edelstain Oct 10 at 9:44
  • $\begingroup$ you have a bit of a mix up with the letters for node c and d, but I got your point $\endgroup$ – ohad edelstain Oct 10 at 10:06
5
$\begingroup$

As Yuval pointed out, there is some ambiguity of the original exercise as the enqueueing order of the neighbors of a node is not stipulated by the definition of a breadth-first-search (BFS).

Proposition 1: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. If $e$ is a part of a cycle, then there is a BFS of $G$ that produces a BFS tree that does not contain $e$. (If $e$ is not part of any cycle, then it is a bridge of $G$ and, hence, appears on every spanning tree.)

Since this proposition is, apparently, clear to the OP, no formal proof will be given here.

If we stick to this (indeterministic) version of BFS, the answer to the exercise should be choice 1, "it does not belong to any cycle".


Let us add some context so that that exercise becomes more interesting.

Suppose that for every node, the order of its children to be enqueued in a BFS is fixed beforehand. Now, it can happen that an edge that is part of a cycle can be part of the spanning tree produced from each of $n$ BFS runs. For example, graph $G_1$ with $C_0=[1,3]$, $C_1=[0,2]$, $C_2=[1,3]$, $C_3=[2,0]$, where $C_i$ is the list of neighbors of node $i$ in the enqueueing order. The following lists shows the edge $\overline{1,2}$ is always part of the BFS tree produced.

  • The BFS starting from node 0 produces the tree with edges $\overline{0, 1}$, $\overline{0,3}$, $\overline{1,2}$.
  • The BFS starting from node 1 produces the tree with edges $\overline{1, 0}$, $\overline{1,2}$, $\overline{0,3}$.
  • The BFS starting from node 2 produces the tree with edges $\overline{2, 1}$, $\overline{2,3}$, $\overline{1,0}$.
  • The BFS starting from node 3 produces the tree with edges $\overline{3, 2}$, $\overline{3,0}$, $\overline{2,1}$.

We have the following proposition.

Proposition 2: Let $G$ be a simple undirected connected graph and $e$ is one of its edges. Suppose we have selected an enqueueing order for the neighbors of each node. If a BFS of $G$ will always include $e$, then $e$ is either not part of any cycle or $e$ is a part of cycle of even length.

Proof. For the sake of contradiction, suppose that there is a cycle of odd length that contains $e$ and every cycle that contains $e$ is of odd length.

Consider $\mathcal C$, one of the shortest cycles that contains $e$. Since the length of $\mathcal C$ is odd, we can select $v_0$, a node of $\mathcal C$ that is "opposite" to $e$, i.e, the cycle is $v_0, v_1, \cdots, v_k, v_{k+1},\cdots, v_{2k-1}, v_{2k}, v_0$ for some $k$ and $v_i$'s, where $\overline{v_k,v_{k+1}}$ is edge $e$. Since any cycle containing $e$ must be longer than $\mathcal C$, we have, $$\text{distance}(v_0, v_{k}) = \text{distance}(v_0, v_{k+1}) = k.$$ Cycle C made with https://graphonline.ru/en/

Let us run BFS from node $v_0$. Let tree $T$ be the BFS tree produced. We claim $T$ does not contain $e$. Otherwise, suppose $T$ does contain $e$. WLOG, suppose $v_k$ is nearer to $v_0$ than $v_{k+1}$. Since $T$ is a shortest-path tree from $v_0$, we have

$$\text{distance}(v_0, v_{k+1}) = \text{distance}(v_0, v_{k}) + \text{distance}(v_k, v_{k+1})=\text{distance}(v_0, v_{k}) + 1,$$

which contradicts previous equality. This contradiction shows that $T$ does not contain $e$. That, however, contradicts the given condition that every BFS tree contains $e$. $\ \checkmark$


With respect to proposition 2, the answer to the exercise should be choice 3, "$e$ might belong to a cycle but if it belongs to an odd-length cycle, then it must belong to an even-length cycle.", if the context, i.e. the way in which BFS is supposed to run, implies that the enqueueing order of neighbors of a node is fixed before all runs.

| cite | improve this answer | |
$\endgroup$

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.