Results 1 to 2 of 2

Math Help - Graph Theory - Trees and Paths

  1. #1
    Member Haven's Avatar
    Joined
    Jul 2009
    Posts
    197
    Thanks
    8

    Graph Theory - Trees and Paths

    I am having difficulties with this problem.

    Let T be a tree with k leaves and set [tex]t=ceiling(k/2)/MATH]. Prove that there exists paths P_1,P_2, \dots P_t which satisfy the following

    i) \cup_{i=1}^{t} P_i = T
    ii) V(P_i) \cap V(P_j) \neq \phi for every i<j.


    EDIT: going over my work i realized that my proof doesn't hold. So I'd appreciate any help on where to start. Induction seems to be the natural choice but i can't get it to work for any parameter.
    Last edited by Haven; October 8th 2010 at 12:12 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member Traveller's Avatar
    Joined
    Sep 2010
    Posts
    162
    Notice that you are required to find paths ending in leaves (except one which is used to cover a single leaf ) that pass through a single common vertex. So you only need to root the tree at a suitable vertex such that the largest of the subtrees (in terms of the number of leaves) of the root does not exceed the sum of the others by more than 1.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory question about trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 27th 2009, 02:52 AM
  2. Graph Theory question about trees
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: November 26th 2009, 03:30 PM
  3. [SOLVED] Graph Theory and Labeled Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2009, 07:10 AM
  4. Graph theory: Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2009, 12:30 PM
  5. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2007, 12:29 AM

Search Tags


/mathhelpforum @mathhelpforum