I Prove that a given graph contains a cycle using induction (Graph Theory)

[Superyoshiom]

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!

 

[fresh_42]

I do not understand this. I guess we may assume that $G\neq \emptyset$. Then if there is no edge, and the number of vertices is less or equal zero, so it has no vertices either and is empty. As we ruled this out, we have at least one edge.

 

[Superyoshiom]

I do not understand this. I guess we may assume that $G\neq \emptyset$. Then if there is no edge, and the number of vertices is less or equal zero, so it has no vertices either and is empty. As we ruled this out, we have at least one edge.

Sorry, I made a type, it should read: 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

I changed the OP to reflect this

 

[fresh_42]

I would perform the induction along the number of vertices, since you cannot control the edges. Your argument for the base is correct. Now assume that every graph with $k < n$ vertices and at least $k$ edges contains at least one cycle.

Now we have a graph with $n$ vertices and no less than $n$ edges, say $m \geq n$ edges. What happens if we remove a vertex and with it possible edges?

 

[Superyoshiom]

I would perform the induction along the number of vertices, since you cannot control the edges. Your argument for the base is correct. Now assume that every graph with $k < n$ vertices and at least $k$ edges contains at least one cycle.

Now we have a graph with $n$ vertices and no less than $n$ edges, say $m \geq n$ edges. What happens if we remove a vertex and with it possible edges?

I guess if we remove a vertex that's adjacent to two or more other vertices we'd end up removing more edges than vertices so we'd get a graph that doesn't follow that rule of V<=E.
If we do that, then should we assume that we'd lose cycles as a result because we are removing potential edges that could be used to form cycles?

 

[fresh_42]

You probably will have to consider cases. If we do not remove an edge, we are done. What happens with two, three etc. many edges removed? And we have still the possibility to remove another vertex. Maybe you should make a table with $m$ and $n$.

 

[Superyoshiom]

You probably will have to consider cases. If we do not remove an edge, we are done. What happens with two, three etc. many edges removed? And we have still the possibility to remove another vertex. Maybe you should make a table with $m$ and $n$.

Here's an idea I got with some research:

For the inductive case, I could have a graph in which the degree of vertices is at least >= 2. Then I find a longest path from v0 to vn, and since we know that v0 is degree 2 or greater, one of those edges from v0 must either connect to a vertex on its path thereby creating a cycle or connect to some outside vertex m, which we can then just add to our longest path.

Since the number of edges must be >= the number of vertices, we can see that a "straight-line" sort of path wouldn't work since something like O---O---O would have three vertices and 2 edges.

At that point, can we just inductively remove vertices and edges until we reach the base case, proving this to be true each time?

 

[jbriggs444]

Why not simply pick any node which has less than or equal to the average number of edges and remove it?

Such a node is guaranteed to exist anywhere outside Lake Wobegon.