Results 1 to 2 of 2

Math Help - Simple Graphs and Paths

  1. #1
    Newbie
    Joined
    May 2009
    Posts
    3

    Simple Graphs and Paths

    This might seem easy, but im having trouble putting my proofs into words.

    Let G = (V,E) be simple graph,

    I need to prove for all vertices (x,y,z) of G, the follwoing are true:

    1) There is a path from x to x.
    2) If there is a path from x to y then there is path y -x.
    3)If there is a path from x- y, and y-z then there is path x-z.

    Now im not sure whats expected when proofing this.

    Do i just say a path from x to x exists since its a path to itself?
    and...
    if a path x-y exists then there is a path y- x because x and y are two connected vertices by a edge?
    and..
    if there is a path from x-y, and y-z then there is a path x-z since vertices x and y are connected by an edge, and y-z is connected by an edge, this provides a path from vertices x to z through vertices y.

    Id like some feedback if possible thanks.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    May 2009
    From
    Tokyo, Japan
    Posts
    46
    Just work from the definitions and find a path that satisfies the conditions.

    1: You can take the vertice sequence {x} which starts and stops at x and exists by axiom.
    2: if F: (a,b,...,z) is the path from x to y, then G: (z,...,b,a) is the path from y to x, which exists because every edge q in G exists by assumption since it exists in F.
    3: if F: (a,b,...,m), G: (n,o...,z) are the respective paths from x to y and from y to z, then the path Ha,b,...,m,n,o,...,z) is the path from x to z, and all edges exist because they existed in F and G.

    I couldn't be arsed with indices of the vertices, which you should use if you do this for homework, but using the alphabet is clearer.

    General rule of thumb when solving these things: don't think too deeply and just construct the answers straight from the definition and question.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: November 10th 2010, 10:02 AM
  2. [SOLVED] Paths in Coloured Graphs
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 7th 2010, 08:37 AM
  3. Dual, k-connected, plane and simple graphs.
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 1st 2010, 10:21 AM
  4. Replies: 5
    Last Post: August 10th 2010, 02:00 AM
  5. Help on Graphs and Paths
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: May 26th 2009, 03:29 AM

Search Tags


/mathhelpforum @mathhelpforum