Mixing
Path Decomposition of a Tree
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Let T be an n-vertex tree with exactly 2k odd-degree vertices. Prove that T decomposes into k paths (i.e. its edge-set is the disjoint union of k paths).
My process so far: For every vertex, you need two neighbors if you are an internal vertex of a path, and one if you are the end vertex of a path. This means a vertex that has an odd degree should be the end vertex of a path. Each path has 2 end vertices, so 2k / 2 = k decompositions will occur.
Do you think this is a formal proof? Do I lack something in my thinking?
graph-theory trees
asked Jul 18 at 14:06
Ninja Bug
132
add a comment |Â
up vote
1
down vote
favorite
Let T be an n-vertex tree with exactly 2k odd-degree vertices. Prove that T decomposes into k paths (i.e. its edge-set is the disjoint union of k paths).
My process so far: For every vertex, you need two neighbors if you are an internal vertex of a path, and one if you are the end vertex of a path. This means a vertex that has an odd degree should be the end vertex of a path. Each path has 2 end vertices, so 2k / 2 = k decompositions will occur.
Do you think this is a formal proof? Do I lack something in my thinking?
graph-theory trees
asked Jul 18 at 14:06
Ninja Bug
132
All you've shown is that if a decomposition into paths exists, it has at least $k$ components. You haven't shown that a decomposition exists, nor that you can do it in exactly $k$ paths (since you haven't ruled out that two distinct paths both begin/end in the same even-degree vertex).
– Mees de Vries
Jul 18 at 14:09
The truth here depends on the definition of tree, path and "decompose". What about a tree with only single vertex. Here $k=0$. Does this tree decompose into zero paths, or do we need one single-vertex-path (if this is considered a path)?
– M. Winter
Jul 18 at 14:35
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Let T be an n-vertex tree with exactly 2k odd-degree vertices. Prove that T decomposes into k paths (i.e. its edge-set is the disjoint union of k paths).
My process so far: For every vertex, you need two neighbors if you are an internal vertex of a path, and one if you are the end vertex of a path. This means a vertex that has an odd degree should be the end vertex of a path. Each path has 2 end vertices, so 2k / 2 = k decompositions will occur.
Do you think this is a formal proof? Do I lack something in my thinking?
graph-theory trees
asked Jul 18 at 14:06
Ninja Bug
132
Let T be an n-vertex tree with exactly 2k odd-degree vertices. Prove that T decomposes into k paths (i.e. its edge-set is the disjoint union of k paths).
My process so far: For every vertex, you need two neighbors if you are an internal vertex of a path, and one if you are the end vertex of a path. This means a vertex that has an odd degree should be the end vertex of a path. Each path has 2 end vertices, so 2k / 2 = k decompositions will occur.
Do you think this is a formal proof? Do I lack something in my thinking?
graph-theory trees
asked Jul 18 at 14:06
Ninja Bug
132
asked Jul 18 at 14:06
Ninja Bug
132
asked Jul 18 at 14:06
Ninja Bug
132
asked Jul 18 at 14:06
Ninja Bug
132
132
All you've shown is that if a decomposition into paths exists, it has at least $k$ components. You haven't shown that a decomposition exists, nor that you can do it in exactly $k$ paths (since you haven't ruled out that two distinct paths both begin/end in the same even-degree vertex).
– Mees de Vries
Jul 18 at 14:09
The truth here depends on the definition of tree, path and "decompose". What about a tree with only single vertex. Here $k=0$. Does this tree decompose into zero paths, or do we need one single-vertex-path (if this is considered a path)?
– M. Winter
Jul 18 at 14:35
add a comment |Â
All you've shown is that if a decomposition into paths exists, it has at least $k$ components. You haven't shown that a decomposition exists, nor that you can do it in exactly $k$ paths (since you haven't ruled out that two distinct paths both begin/end in the same even-degree vertex).
– Mees de Vries
Jul 18 at 14:09
The truth here depends on the definition of tree, path and "decompose". What about a tree with only single vertex. Here $k=0$. Does this tree decompose into zero paths, or do we need one single-vertex-path (if this is considered a path)?
– M. Winter
Jul 18 at 14:35
All you've shown is that if a decomposition into paths exists, it has at least $k$ components. You haven't shown that a decomposition exists, nor that you can do it in exactly $k$ paths (since you haven't ruled out that two distinct paths both begin/end in the same even-degree vertex).
– Mees de Vries
Jul 18 at 14:09
All you've shown is that if a decomposition into paths exists, it has at least $k$ components. You haven't shown that a decomposition exists, nor that you can do it in exactly $k$ paths (since you haven't ruled out that two distinct paths both begin/end in the same even-degree vertex).
– Mees de Vries
Jul 18 at 14:09
The truth here depends on the definition of tree, path and "decompose". What about a tree with only single vertex. Here $k=0$. Does this tree decompose into zero paths, or do we need one single-vertex-path (if this is considered a path)?
– M. Winter
Jul 18 at 14:35
The truth here depends on the definition of tree, path and "decompose". What about a tree with only single vertex. Here $k=0$. Does this tree decompose into zero paths, or do we need one single-vertex-path (if this is considered a path)?
– M. Winter
Jul 18 at 14:35
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
0
down vote
accepted
The other have pointed out the incompleteness of your proof. Let me show you how to find the actual paths.
Actually, let's show it more generally for forests (which consist of one or more disjoint trees). This makes it easiert to use induction w.r.t. the number of odd-degree vertices.
Induction start: ($2k=0$)
In general, if a tree has more than one vertex, then it has at least two leaves (this must be proven, but I assume you can do this), and every leaf is of odd degree (of degree one to be precise). Hence, a forest with no odd-degree vertices can only consist of isolated vertices (one-vertex-trees). Assuming a suitable definition of "decompose", we can argue that a graph without edges can be decomposed into $k=0$ paths.
Induction step: ($2kto 2k-2$)
Let's say the forest $F$ has $2k>0$ odd-degree vertices. There must be a tree $Tsubseteq F$ in the forest which has more than one vertex. This tree has at least two leaves, say $a,bin T$. Let $P$ be the path in $T$ that connects $a$ and $b$. Construct $F'$ from $F$ by removing the edges of $P$ from $F$. Now, in $F'$ the vertices $a$ and $b$ are isolated (because they were of degree one in $T$). So, these are no longer of odd degree. The other vertices of $P$ lost two edges each, i.e. the parity of their degree has not changed. Thus, $F'$ has exactly two odd-degree vertices fewer than $F$, i.e. $2k-2$ many. So by induction hypothesis it decomposes into $k-1$ paths, and together with $P$ we have the $k$ decomposing paths of $F$.
$square$
answered Jul 19 at 9:27
M. Winter
17.7k62764
add a comment |Â
up vote
1
down vote
Your argument just says we can identify the right number of ends; it doesn't prove that you can actually find a system of paths with these ends, and even if you could it wouldn't prove that there aren't any edges left over. Crucially, you haven't used the fact that your graph is a tree, and without that fact the result wouldn't be true.
Hint for an actual proof: add $k$ extra edges to get a graph with all degrees even, and use the fact that this modified graph is Eulerian.
answered Jul 18 at 14:24
Especially Lime
19.1k22252
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
0
down vote
accepted
The other have pointed out the incompleteness of your proof. Let me show you how to find the actual paths.
Actually, let's show it more generally for forests (which consist of one or more disjoint trees). This makes it easiert to use induction w.r.t. the number of odd-degree vertices.
Induction start: ($2k=0$)
In general, if a tree has more than one vertex, then it has at least two leaves (this must be proven, but I assume you can do this), and every leaf is of odd degree (of degree one to be precise). Hence, a forest with no odd-degree vertices can only consist of isolated vertices (one-vertex-trees). Assuming a suitable definition of "decompose", we can argue that a graph without edges can be decomposed into $k=0$ paths.
Induction step: ($2kto 2k-2$)
Let's say the forest $F$ has $2k>0$ odd-degree vertices. There must be a tree $Tsubseteq F$ in the forest which has more than one vertex. This tree has at least two leaves, say $a,bin T$. Let $P$ be the path in $T$ that connects $a$ and $b$. Construct $F'$ from $F$ by removing the edges of $P$ from $F$. Now, in $F'$ the vertices $a$ and $b$ are isolated (because they were of degree one in $T$). So, these are no longer of odd degree. The other vertices of $P$ lost two edges each, i.e. the parity of their degree has not changed. Thus, $F'$ has exactly two odd-degree vertices fewer than $F$, i.e. $2k-2$ many. So by induction hypothesis it decomposes into $k-1$ paths, and together with $P$ we have the $k$ decomposing paths of $F$.
$square$
answered Jul 19 at 9:27
M. Winter
17.7k62764
add a comment |Â
up vote
0
down vote
accepted
The other have pointed out the incompleteness of your proof. Let me show you how to find the actual paths.
Actually, let's show it more generally for forests (which consist of one or more disjoint trees). This makes it easiert to use induction w.r.t. the number of odd-degree vertices.
Induction start: ($2k=0$)
In general, if a tree has more than one vertex, then it has at least two leaves (this must be proven, but I assume you can do this), and every leaf is of odd degree (of degree one to be precise). Hence, a forest with no odd-degree vertices can only consist of isolated vertices (one-vertex-trees). Assuming a suitable definition of "decompose", we can argue that a graph without edges can be decomposed into $k=0$ paths.
Induction step: ($2kto 2k-2$)
Let's say the forest $F$ has $2k>0$ odd-degree vertices. There must be a tree $Tsubseteq F$ in the forest which has more than one vertex. This tree has at least two leaves, say $a,bin T$. Let $P$ be the path in $T$ that connects $a$ and $b$. Construct $F'$ from $F$ by removing the edges of $P$ from $F$. Now, in $F'$ the vertices $a$ and $b$ are isolated (because they were of degree one in $T$). So, these are no longer of odd degree. The other vertices of $P$ lost two edges each, i.e. the parity of their degree has not changed. Thus, $F'$ has exactly two odd-degree vertices fewer than $F$, i.e. $2k-2$ many. So by induction hypothesis it decomposes into $k-1$ paths, and together with $P$ we have the $k$ decomposing paths of $F$.
$square$
answered Jul 19 at 9:27
M. Winter
17.7k62764
add a comment |Â
up vote
0
down vote
accepted
up vote
0
down vote
accepted
The other have pointed out the incompleteness of your proof. Let me show you how to find the actual paths.
Actually, let's show it more generally for forests (which consist of one or more disjoint trees). This makes it easiert to use induction w.r.t. the number of odd-degree vertices.
Induction start: ($2k=0$)
In general, if a tree has more than one vertex, then it has at least two leaves (this must be proven, but I assume you can do this), and every leaf is of odd degree (of degree one to be precise). Hence, a forest with no odd-degree vertices can only consist of isolated vertices (one-vertex-trees). Assuming a suitable definition of "decompose", we can argue that a graph without edges can be decomposed into $k=0$ paths.
Induction step: ($2kto 2k-2$)
Let's say the forest $F$ has $2k>0$ odd-degree vertices. There must be a tree $Tsubseteq F$ in the forest which has more than one vertex. This tree has at least two leaves, say $a,bin T$. Let $P$ be the path in $T$ that connects $a$ and $b$. Construct $F'$ from $F$ by removing the edges of $P$ from $F$. Now, in $F'$ the vertices $a$ and $b$ are isolated (because they were of degree one in $T$). So, these are no longer of odd degree. The other vertices of $P$ lost two edges each, i.e. the parity of their degree has not changed. Thus, $F'$ has exactly two odd-degree vertices fewer than $F$, i.e. $2k-2$ many. So by induction hypothesis it decomposes into $k-1$ paths, and together with $P$ we have the $k$ decomposing paths of $F$.
$square$
answered Jul 19 at 9:27
M. Winter
17.7k62764
The other have pointed out the incompleteness of your proof. Let me show you how to find the actual paths.
Actually, let's show it more generally for forests (which consist of one or more disjoint trees). This makes it easiert to use induction w.r.t. the number of odd-degree vertices.
Induction start: ($2k=0$)
In general, if a tree has more than one vertex, then it has at least two leaves (this must be proven, but I assume you can do this), and every leaf is of odd degree (of degree one to be precise). Hence, a forest with no odd-degree vertices can only consist of isolated vertices (one-vertex-trees). Assuming a suitable definition of "decompose", we can argue that a graph without edges can be decomposed into $k=0$ paths.
Induction step: ($2kto 2k-2$)
Let's say the forest $F$ has $2k>0$ odd-degree vertices. There must be a tree $Tsubseteq F$ in the forest which has more than one vertex. This tree has at least two leaves, say $a,bin T$. Let $P$ be the path in $T$ that connects $a$ and $b$. Construct $F'$ from $F$ by removing the edges of $P$ from $F$. Now, in $F'$ the vertices $a$ and $b$ are isolated (because they were of degree one in $T$). So, these are no longer of odd degree. The other vertices of $P$ lost two edges each, i.e. the parity of their degree has not changed. Thus, $F'$ has exactly two odd-degree vertices fewer than $F$, i.e. $2k-2$ many. So by induction hypothesis it decomposes into $k-1$ paths, and together with $P$ we have the $k$ decomposing paths of $F$.
$square$
answered Jul 19 at 9:27
M. Winter
17.7k62764
answered Jul 19 at 9:27
M. Winter
17.7k62764
answered Jul 19 at 9:27
M. Winter
17.7k62764
answered Jul 19 at 9:27
M. Winter
17.7k62764
17.7k62764
add a comment |Â
add a comment |Â
up vote
1
down vote
Your argument just says we can identify the right number of ends; it doesn't prove that you can actually find a system of paths with these ends, and even if you could it wouldn't prove that there aren't any edges left over. Crucially, you haven't used the fact that your graph is a tree, and without that fact the result wouldn't be true.
Hint for an actual proof: add $k$ extra edges to get a graph with all degrees even, and use the fact that this modified graph is Eulerian.
answered Jul 18 at 14:24
Especially Lime
19.1k22252
add a comment |Â
up vote
1
down vote
Your argument just says we can identify the right number of ends; it doesn't prove that you can actually find a system of paths with these ends, and even if you could it wouldn't prove that there aren't any edges left over. Crucially, you haven't used the fact that your graph is a tree, and without that fact the result wouldn't be true.
Hint for an actual proof: add $k$ extra edges to get a graph with all degrees even, and use the fact that this modified graph is Eulerian.
answered Jul 18 at 14:24
Especially Lime
19.1k22252
add a comment |Â
up vote
1
down vote
up vote
1
down vote
Your argument just says we can identify the right number of ends; it doesn't prove that you can actually find a system of paths with these ends, and even if you could it wouldn't prove that there aren't any edges left over. Crucially, you haven't used the fact that your graph is a tree, and without that fact the result wouldn't be true.
Hint for an actual proof: add $k$ extra edges to get a graph with all degrees even, and use the fact that this modified graph is Eulerian.
answered Jul 18 at 14:24
Especially Lime
19.1k22252
Your argument just says we can identify the right number of ends; it doesn't prove that you can actually find a system of paths with these ends, and even if you could it wouldn't prove that there aren't any edges left over. Crucially, you haven't used the fact that your graph is a tree, and without that fact the result wouldn't be true.
Hint for an actual proof: add $k$ extra edges to get a graph with all degrees even, and use the fact that this modified graph is Eulerian.
answered Jul 18 at 14:24
Especially Lime
19.1k22252
answered Jul 18 at 14:24
Especially Lime
19.1k22252
answered Jul 18 at 14:24
Especially Lime
19.1k22252
answered Jul 18 at 14:24
Especially Lime
19.1k22252
19.1k22252
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2855612%2fpath-decomposition-of-a-tree%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
All you've shown is that if a decomposition into paths exists, it has at least $k$ components. You haven't shown that a decomposition exists, nor that you can do it in exactly $k$ paths (since you haven't ruled out that two distinct paths both begin/end in the same even-degree vertex).
– Mees de Vries
Jul 18 at 14:09
The truth here depends on the definition of tree, path and "decompose". What about a tree with only single vertex. Here $k=0$. Does this tree decompose into zero paths, or do we need one single-vertex-path (if this is considered a path)?
– M. Winter
Jul 18 at 14:35