- #1
Superyoshiom
- 29
- 0
My Problem: Given a Graph G = (V,E), where the number of vertices is less than or equal to the number of edges, use induction to prove that the graph contains at least one cycle (the graph is not required to be completely connected).
My attempt: For my base case, I used only one vertex with one edge, and if I just made the edge connect the vertex to itself, that would form a cycle. The inductive case is where I'm having trouble with this problem. At first, I thought that I could have k number of vertices for a graph, and that current graph would contain at least one cycle. Then that would lead me to two cases: we could add a k+1 vertex to our connected graph and still have that original cycle intact or put the k+1 vertex by itself, thereby creating at least two cycles, one from the original k vertices and one cycle of the k+1 vertex connected to itself.
However, the professor said this would be an example of weak induction, and that there are many more cases to take into account when solving that type of induction, so to use strong induction instead. However, aside from the base case, I'm unsure as to how I would use strong induction to solve this problem. One thought I have is to assume that I have a graph that already contains a cycle, and then start removing vertices and edges to see if it still contains a cycle, but I still see that as running into the same problems as before.
Thanks for the help in advance!
My attempt: For my base case, I used only one vertex with one edge, and if I just made the edge connect the vertex to itself, that would form a cycle. The inductive case is where I'm having trouble with this problem. At first, I thought that I could have k number of vertices for a graph, and that current graph would contain at least one cycle. Then that would lead me to two cases: we could add a k+1 vertex to our connected graph and still have that original cycle intact or put the k+1 vertex by itself, thereby creating at least two cycles, one from the original k vertices and one cycle of the k+1 vertex connected to itself.
However, the professor said this would be an example of weak induction, and that there are many more cases to take into account when solving that type of induction, so to use strong induction instead. However, aside from the base case, I'm unsure as to how I would use strong induction to solve this problem. One thought I have is to assume that I have a graph that already contains a cycle, and then start removing vertices and edges to see if it still contains a cycle, but I still see that as running into the same problems as before.
Thanks for the help in advance!
Last edited: