Results 1 to 4 of 4

Math Help - Help on Graphs and Paths

  1. #1
    Junior Member
    Joined
    Mar 2009
    Posts
    44

    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.

    Someone please help me out on this one.


    Thanks,
    Kurac.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by kurac View Post
    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.

    Quote Originally Posted by kurac View Post
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Mar 2009
    Posts
    44
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by kurac View Post
    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Paths in Coloured Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 7th 2010, 09:37 AM
  2. 3d Object paths
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 25th 2009, 11:17 PM
  3. Simple Graphs and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 9th 2009, 10:10 AM
  4. How many paths...?
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: March 14th 2008, 08:54 AM
  5. Integration along Paths
    Posted in the Calculus Forum
    Replies: 3
    Last Post: June 6th 2007, 05:35 PM

Search Tags


/mathhelpforum @mathhelpforum