What is the lower bound of number of degree 1 vertices of a tree with no degree 2 vertices?
up vote
1
down vote
favorite
Here is the question:
Let $G$ be a tree with $n$ vertices, and no vertex in the tree has degree $2$. Find a function of $n$ that indicates the lower bound of the number of degree $1$ vertices in the tree.
with handshake lemma and Euler's formula, I get $n_1 =2 + sum_{k =3}^{infty} (k-2)n_k$ where $n_k$ is the number of degree $k$ vertices. However, this result cannot tell me the lower bound of $n_1$.
I guess the result is $n -biglfloor frac{n}{2} bigrfloor$, but not sure how to prove this.
Please give me some hint, thank you.
graph-theory trees
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
asked Nov 15 at 4:53
Enllwx
112
add a comment |
up vote
1
down vote
favorite
Here is the question:
Let $G$ be a tree with $n$ vertices, and no vertex in the tree has degree $2$. Find a function of $n$ that indicates the lower bound of the number of degree $1$ vertices in the tree.
with handshake lemma and Euler's formula, I get $n_1 =2 + sum_{k =3}^{infty} (k-2)n_k$ where $n_k$ is the number of degree $k$ vertices. However, this result cannot tell me the lower bound of $n_1$.
I guess the result is $n -biglfloor frac{n}{2} bigrfloor$, but not sure how to prove this.
Please give me some hint, thank you.
graph-theory trees
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
asked Nov 15 at 4:53
Enllwx
112
math.stackexchange.com/questions/1484941/…
– Alexander Gruber♦
Nov 15 at 4:59
add a comment |
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Here is the question:
Let $G$ be a tree with $n$ vertices, and no vertex in the tree has degree $2$. Find a function of $n$ that indicates the lower bound of the number of degree $1$ vertices in the tree.
with handshake lemma and Euler's formula, I get $n_1 =2 + sum_{k =3}^{infty} (k-2)n_k$ where $n_k$ is the number of degree $k$ vertices. However, this result cannot tell me the lower bound of $n_1$.
I guess the result is $n -biglfloor frac{n}{2} bigrfloor$, but not sure how to prove this.
Please give me some hint, thank you.
graph-theory trees
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
asked Nov 15 at 4:53
Enllwx
112
Here is the question:
Let $G$ be a tree with $n$ vertices, and no vertex in the tree has degree $2$. Find a function of $n$ that indicates the lower bound of the number of degree $1$ vertices in the tree.
with handshake lemma and Euler's formula, I get $n_1 =2 + sum_{k =3}^{infty} (k-2)n_k$ where $n_k$ is the number of degree $k$ vertices. However, this result cannot tell me the lower bound of $n_1$.
I guess the result is $n -biglfloor frac{n}{2} bigrfloor$, but not sure how to prove this.
Please give me some hint, thank you.
graph-theory trees
graph-theory trees
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
asked Nov 15 at 4:53
Enllwx
112
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
asked Nov 15 at 4:53
Enllwx
112
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
edited Nov 15 at 5:01
Alexander Gruber♦
20.1k24102171
20.1k24102171
asked Nov 15 at 4:53
Enllwx
112
asked Nov 15 at 4:53
Enllwx
112
asked Nov 15 at 4:53
Enllwx
112
112
math.stackexchange.com/questions/1484941/…
– Alexander Gruber♦
Nov 15 at 4:59
add a comment |
math.stackexchange.com/questions/1484941/…
– Alexander Gruber♦
Nov 15 at 4:59
math.stackexchange.com/questions/1484941/…
– Alexander Gruber♦
Nov 15 at 4:59
math.stackexchange.com/questions/1484941/…
– Alexander Gruber♦
Nov 15 at 4:59
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
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
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2999230%2fwhat-is-the-lower-bound-of-number-of-degree-1-vertices-of-a-tree-with-no-degree%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
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
Required, but never shown
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
Required, but never shown
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
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
math.stackexchange.com/questions/1484941/…
– Alexander Gruber♦
Nov 15 at 4:59