Results 1 to 7 of 7

Thread: Graph Theory

  1. #1
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Question Graph Theory

    Please correct me where wrong:

    Graph Theory-ggffd.png
    Assumption 1 to the solution:

    Answer (b):
    This can be prove as follows:
    Direct Proof:
    Let us consider the longest path {v0, v1},{v1, v2},...,{vn-1, vn} between two vertices x = v0 and y = vn in the tree (here the length of a path is how many edges it uses, and if there are multiple longest paths then we just pick one of them).
    We claim that x and y must be leaves.
    Suppose the contrary that x is not a leaf, so it has degree at least two (as we know that every node except root or leaf has at least degree 2).
    This means x is adjacent to another vertex z different from v1. Observe that z cannot appear in the path from x to y that we are considering, for otherwise there would be a cycle in the tree. Therefore, we can add the edge {z, x} to our path to obtain a longer path in the tree, contradicting our earlier choice of the longest path. Thus, we conclude that x is a leaf.
    By the same argument, we conclude y is also a leaf.
    Thus we conclude that every tree with at least two vertices has at least two leaves.



    Assumption 2 to the solution:

    b)
    If a tree has only 2 vertices.. then their degrees must be one...based on the definition on the tree...
    so..we have 2 vertices with the degree two means..we have two leaves...
    so...for every tree with at least two vertices has at least two leaves


    Please could someone tell me which one is better and add details that may need specifying, thanks




    (Part a my overall assumption)
    -
    A graph G is connected if for every pair of vertices u and v of G there is a path
    from u to v. Otherwise G is disconnected.
    -
    A tree is a connected graph with no cycles.
    -
    A leaf is a vertex of degree 1.
    Last edited by inayat; May 18th 2018 at 06:31 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,571
    Thanks
    1437

    Re: Graph Theory

    Quote Originally Posted by inayat View Post
    Please correct me where wrong:

    Click image for larger version. 

Name:	ggffd.png 
Views:	7 
Size:	45.5 KB 
ID:	38744
    Assumption 1 to the solution:

    Answer (b):
    This can be prove as follows:
    Direct Proof:
    Let us consider the longest path {v0, v1},{v1, v2},...,{vn-1, vn} between two vertices x = v0 and y = vn in the tree (here the length of a path is how many edges it uses, and if there are multiple longest paths then we just pick one of them).
    We claim that x and y must be leaves.
    Suppose the contrary that x is not a leaf, so it has degree at least two (as we know that every node except root or leaf has at least degree 2).
    This means x is adjacent to another vertex z different from v1. Observe that z cannot appear in the path from x to y that we are considering, for otherwise there would be a cycle in the tree. Therefore, we can add the edge {z, x} to our path to obtain a longer path in the tree, contradicting our earlier choice of the longest path. Thus, we conclude that x is a leaf.
    By the same argument, we conclude y is also a leaf.
    Thus we conclude that every tree with at least two vertices has at least two leaves.



    Assumption 2 to the solution:

    b)
    If a tree has only 2 vertices.. then their degrees must be one...based on the definition on the tree...
    so..we have 2 vertices with the degree two means..we have two leaves...
    so...for every tree with at least two vertices has at least two leaves


    Please could someone tell me which one is better and add details that may need specifying, thanks




    (Part a my overall assumption)
    -
    A graph G is connected if for every pair of vertices u and v of G there is a path
    from u to v. Otherwise G is disconnected.
    -
    A tree is a connected graph with no cycles.
    -
    A leaf is a vertex of degree 1.
    You need to define "longest path" because it is not obvious. Consider the following graph:

    a----b----c----d

    You want the longest path between b and c. Is that b,a,b,a,...,b,c where you jump back and forth between a and b a nigh infinite number of times? Because if that is the case, it is easy to show that a longest path does not exist between those two vertices. And it is easy to see that neither b nor c is a leaf.

    I believe what you are looking for is to choose two vertices such that the shortest path between them is maximal. In other words, you cannot add any additional vertices to make the shortest path between them longer.

    Your second attempt is not a proof at all.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Re: Graph Theory

    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,571
    Thanks
    1437

    Re: Graph Theory

    Quote Originally Posted by inayat View Post
    What is your question?
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Nov 2017
    From
    South Asia
    Posts
    43

    Re: Graph Theory

    Quote Originally Posted by SlipEternal View Post
    What is your question?
    Thats the answer to part (b)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Nov 2010
    Posts
    3,571
    Thanks
    1437

    Re: Graph Theory

    Quote Originally Posted by inayat View Post
    Thats the answer to part (b)
    I am not going to follow a random link. I'll take your word for it.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    MHF Contributor

    Joined
    Aug 2006
    Posts
    21,880
    Thanks
    2890
    Awards
    1

    Re: Graph Theory

    Quote Originally Posted by inayat View Post
    Click image for larger version. 

Name:	ggffd.png 
Views:	7 
Size:	45.5 KB 
ID:	38744
    Please could someone tell me which one is better and add details that may need specifying, thanks[/FONT][/COLOR]
    (Part a my overall assumption)
    -
    A graph G is connected if for every pair of vertices u and v of G there is a path
    from u to v. Otherwise G is disconnected.
    -
    A tree is a connected graph with no cycles.
    -
    A leaf is a vertex of degree 1.
    Suppose that $\mathcal{T}$ is a tree with at least two vertices: $v_1,v_2,\cdots,v_n$
    Being a tree the graph has $n-1$ edges. By a theorem $\sum\limits_{k = 1}^n {\deg ({v_k})} = 2(n - 1) = 2n - 2$ .
    How do we know that some vertex has degree $1~?$
    From that where can you go?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: Mar 30th 2012, 02:27 AM
  2. Graph Theory / Chromatic Number of a Complete Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Nov 15th 2011, 09:59 AM
  3. (Graph Theory)Prove that graph X is a tree.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Aug 1st 2011, 03:30 AM
  4. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM

/mathhelpforum @mathhelpforum