New answers tagged

0

Assuming the graph has no cycles in it, the graph is hence a tree. Since in a tree, there is a unique path between two vertices, we will never encounter a visited vertex and hence our algorithm will not detect a cycle. Now assuming there is at least one cycle in the graph. Consider the set $S$ of vertices, that belong to a cycle and have the least possible ...


0

An implication is true if the antecedent is false. If j is 1 then the antecedent is false no matter what k you choose, which means that the implication is vacuously true for every k. So the assertion is true.


Top 50 recent answers are included