# Thread: Help on Graphs and Paths

1. ## Help on Graphs and Paths

Hi I have two problems I need help with.

1) Prove that if G is a connected simple graph and e is an edge of a simple circuit in G then the graph G without the edge e is still connected.

So, this is what i thought: Since by definition of a connected graph, a connected graph is connected if there is a path between every pair of vertices of the graph. So by removing the edge e, the remainding graph is still connected.
Can someone help me out on this, I dont think thats a correct proof.

This next question puzzles me and I have even tried drawing it to help my understanding but I stil ldont get it.
2) Let G be a directed graph with n vertices. Assume that for vertices x and y in G there is a path from x to y such that the length of the path is greater than or equal to n.
So the question is why is there infinitely many paths from x to y.

Thanks,
Kurac.

2. Originally Posted by kurac
1) Prove that if G is a connected simple graph and e is an edge of a simple circuit in G then the graph G without the edge e is still connected.

So, this is what i thought: Since by definition of a connected graph, a connected graph is connected if there is a path between every pair of vertices of the graph. So by removing the edge e, the remainding graph is still connected.
Can someone help me out on this, I dont think thats a correct proof.
Essentially, it is because e is on a simple circuit you can get to the vertices connected to e going the other way along the circuit.

Removing an edge will only ever remove the connectivity of a graph if that edge is the only way to get from one section of the graph to another - if that edge forms a bridge. As it is on a simple circuit this is not the case.

Originally Posted by kurac
This next question puzzles me and I have even tried drawing it to help my understanding but I stil ldont get it.
2) Let G be a directed graph with n vertices. Assume that for vertices x and y in G there is a path from x to y such that the length of the path is greater than or equal to n.
So the question is why is there infinitely many paths from x to y.
Here, we want to find loops. What can you say about the minimum number of edges of the graph? Can you use this result to show that a loop exists? That is to say, do we arrive at the same point at least twice?

3. I still dont understand how if n = 4 for example, we have a square graph which is directed. I still dont see how there are loops? There is only one way from x to y in a square.

4. Originally Posted by kurac
I still dont understand how if n = 4 for example, we have a square graph which is directed. I still dont see how there are loops? There is only one way from x to y in a square.
You have a directed graph where you can get from $x$ to $y$ by traversing at least 4 vertices. Then,

If $x=y$ you can just keep going, and so you have infinitely many paths.

If $x \neq y$ then there must be an edge which you are allowed to traverse in either direction. So you can traverse it however many times you like, and so you have infinite paths.