Mixing
![Discrete mathematics / set theory [closed]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Proposition: A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices.
Assuming that $d > 2$ and $k > 3$, improve the bound in above proposition to $d^k$.
The above question is from exercise problem in Diestel's book. How can we formally prove this?
combinatorics discrete-mathematics graph-theory
asked Jul 30 at 17:21
Möbius
155
add a comment |Â
up vote
2
down vote
favorite
Proposition: A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices.
Assuming that $d > 2$ and $k > 3$, improve the bound in above proposition to $d^k$.
The above question is from exercise problem in Diestel's book. How can we formally prove this?
combinatorics discrete-mathematics graph-theory
asked Jul 30 at 17:21
Möbius
155
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Proposition: A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices.
Assuming that $d > 2$ and $k > 3$, improve the bound in above proposition to $d^k$.
The above question is from exercise problem in Diestel's book. How can we formally prove this?
combinatorics discrete-mathematics graph-theory
asked Jul 30 at 17:21
Möbius
155
Proposition: A graph $G$ of radius at most $k$ and maximum degree at most $d$ has no more than $1 + kd^k$ vertices.
Assuming that $d > 2$ and $k > 3$, improve the bound in above proposition to $d^k$.
The above question is from exercise problem in Diestel's book. How can we formally prove this?
combinatorics discrete-mathematics graph-theory
asked Jul 30 at 17:21
Möbius
155
edited Jul 30 at 17:59
asked Jul 30 at 17:21
Möbius
155
asked Jul 30 at 17:21
Möbius
155
asked Jul 30 at 17:21
Möbius
155
155
add a comment |Â
add a comment |Â
2 Answers
2
active
oldest
votes
up vote
1
down vote
accepted
Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$. Fix a center $uin V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph). A vertex $vin V$ is of level $lin0,1,2,ldots,k$ if the shortest path from $u$ to $v$ is of length $l$. Write $N_l$ for the number of vertices of level $l$.
First, $N_0=1$. Thus, $N_1leq d$. We can easily seen that $$N_l+1leq (d-1),N_ltext for l=1,2,ldots,k-1,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$. That is,
$$N_lleq d,(d-1)^l-1text for l=1,2,3,ldots,k,.$$
If $d>2$, then
$$beginalign
|V|&= sum_l=0^k,N_lleq 1+d,sum_l=1^k,(d-1)^l-1leq 1+kd(d-1)^k-1leq 1+kd^k,.
endalign$$
If $d=2$, then obviously, $N_lleq 2$ for all $l=1,2,ldots,k$, whence
$$|V|leq 1+2kleq 1+kd^k,.$$
If $d=1$, then the graph consist of at most $2$ vertices, so
$$|V|leq 2leq 1+kd^k,,$$
as $kgeq 1$.
The inequalities
$$|V|leq 1+d,sum_l=1^k,(d-1)^l-1=left{
beginarrayll
1+dleft(frac(d-1)^k-1(d-1)-1right),,&text for dneq 2,,\
1+2k,,&text for d=2,,endarrayright.$$
are sharp, and stronger than the original inequality $|V|leq 1+kd^k$. An example in each case should be easy to find. We can also show that $|V|< d^k$ for $dgeq 2$ and $kgeq 3$. The case $d=2$ is trivial. For $d>2$, we note that
$$beginalign(d-2),left(fracd^k-1dright)&> (d-2),left(d^k-1-1 right) = d^2(d-2),d^k-3-(d-2)
\
&> left((d-1)^3+d^2right),d^k-3-(d-2)geq (d-1)^3,d^k-3+d^2-(d-2)
\
&>(d-1)^3,d^k-3-1geq (d-1)^k-1,,endalign$$
whence
$$|V|leq 1+d,left(frac(d-1)^k-1d-2right)<d^k,.$$
answered Jul 30 at 17:59
Batominovski
22.8k22777
add a comment |Â
up vote
2
down vote
Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation
$$
1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+dots = 1+sum_i=0^k-1d(d-1)^i
$$
Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
accepted
Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$. Fix a center $uin V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph). A vertex $vin V$ is of level $lin0,1,2,ldots,k$ if the shortest path from $u$ to $v$ is of length $l$. Write $N_l$ for the number of vertices of level $l$.
First, $N_0=1$. Thus, $N_1leq d$. We can easily seen that $$N_l+1leq (d-1),N_ltext for l=1,2,ldots,k-1,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$. That is,
$$N_lleq d,(d-1)^l-1text for l=1,2,3,ldots,k,.$$
If $d>2$, then
$$beginalign
|V|&= sum_l=0^k,N_lleq 1+d,sum_l=1^k,(d-1)^l-1leq 1+kd(d-1)^k-1leq 1+kd^k,.
endalign$$
If $d=2$, then obviously, $N_lleq 2$ for all $l=1,2,ldots,k$, whence
$$|V|leq 1+2kleq 1+kd^k,.$$
If $d=1$, then the graph consist of at most $2$ vertices, so
$$|V|leq 2leq 1+kd^k,,$$
as $kgeq 1$.
The inequalities
$$|V|leq 1+d,sum_l=1^k,(d-1)^l-1=left{
beginarrayll
1+dleft(frac(d-1)^k-1(d-1)-1right),,&text for dneq 2,,\
1+2k,,&text for d=2,,endarrayright.$$
are sharp, and stronger than the original inequality $|V|leq 1+kd^k$. An example in each case should be easy to find. We can also show that $|V|< d^k$ for $dgeq 2$ and $kgeq 3$. The case $d=2$ is trivial. For $d>2$, we note that
$$beginalign(d-2),left(fracd^k-1dright)&> (d-2),left(d^k-1-1 right) = d^2(d-2),d^k-3-(d-2)
\
&> left((d-1)^3+d^2right),d^k-3-(d-2)geq (d-1)^3,d^k-3+d^2-(d-2)
\
&>(d-1)^3,d^k-3-1geq (d-1)^k-1,,endalign$$
whence
$$|V|leq 1+d,left(frac(d-1)^k-1d-2right)<d^k,.$$
answered Jul 30 at 17:59
Batominovski
22.8k22777
add a comment |Â
up vote
1
down vote
accepted
Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$. Fix a center $uin V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph). A vertex $vin V$ is of level $lin0,1,2,ldots,k$ if the shortest path from $u$ to $v$ is of length $l$. Write $N_l$ for the number of vertices of level $l$.
First, $N_0=1$. Thus, $N_1leq d$. We can easily seen that $$N_l+1leq (d-1),N_ltext for l=1,2,ldots,k-1,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$. That is,
$$N_lleq d,(d-1)^l-1text for l=1,2,3,ldots,k,.$$
If $d>2$, then
$$beginalign
|V|&= sum_l=0^k,N_lleq 1+d,sum_l=1^k,(d-1)^l-1leq 1+kd(d-1)^k-1leq 1+kd^k,.
endalign$$
If $d=2$, then obviously, $N_lleq 2$ for all $l=1,2,ldots,k$, whence
$$|V|leq 1+2kleq 1+kd^k,.$$
If $d=1$, then the graph consist of at most $2$ vertices, so
$$|V|leq 2leq 1+kd^k,,$$
as $kgeq 1$.
The inequalities
$$|V|leq 1+d,sum_l=1^k,(d-1)^l-1=left{
beginarrayll
1+dleft(frac(d-1)^k-1(d-1)-1right),,&text for dneq 2,,\
1+2k,,&text for d=2,,endarrayright.$$
are sharp, and stronger than the original inequality $|V|leq 1+kd^k$. An example in each case should be easy to find. We can also show that $|V|< d^k$ for $dgeq 2$ and $kgeq 3$. The case $d=2$ is trivial. For $d>2$, we note that
$$beginalign(d-2),left(fracd^k-1dright)&> (d-2),left(d^k-1-1 right) = d^2(d-2),d^k-3-(d-2)
\
&> left((d-1)^3+d^2right),d^k-3-(d-2)geq (d-1)^3,d^k-3+d^2-(d-2)
\
&>(d-1)^3,d^k-3-1geq (d-1)^k-1,,endalign$$
whence
$$|V|leq 1+d,left(frac(d-1)^k-1d-2right)<d^k,.$$
answered Jul 30 at 17:59
Batominovski
22.8k22777
add a comment |Â
up vote
1
down vote
accepted
up vote
1
down vote
accepted
Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$. Fix a center $uin V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph). A vertex $vin V$ is of level $lin0,1,2,ldots,k$ if the shortest path from $u$ to $v$ is of length $l$. Write $N_l$ for the number of vertices of level $l$.
First, $N_0=1$. Thus, $N_1leq d$. We can easily seen that $$N_l+1leq (d-1),N_ltext for l=1,2,ldots,k-1,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$. That is,
$$N_lleq d,(d-1)^l-1text for l=1,2,3,ldots,k,.$$
If $d>2$, then
$$beginalign
|V|&= sum_l=0^k,N_lleq 1+d,sum_l=1^k,(d-1)^l-1leq 1+kd(d-1)^k-1leq 1+kd^k,.
endalign$$
If $d=2$, then obviously, $N_lleq 2$ for all $l=1,2,ldots,k$, whence
$$|V|leq 1+2kleq 1+kd^k,.$$
If $d=1$, then the graph consist of at most $2$ vertices, so
$$|V|leq 2leq 1+kd^k,,$$
as $kgeq 1$.
The inequalities
$$|V|leq 1+d,sum_l=1^k,(d-1)^l-1=left{
beginarrayll
1+dleft(frac(d-1)^k-1(d-1)-1right),,&text for dneq 2,,\
1+2k,,&text for d=2,,endarrayright.$$
are sharp, and stronger than the original inequality $|V|leq 1+kd^k$. An example in each case should be easy to find. We can also show that $|V|< d^k$ for $dgeq 2$ and $kgeq 3$. The case $d=2$ is trivial. For $d>2$, we note that
$$beginalign(d-2),left(fracd^k-1dright)&> (d-2),left(d^k-1-1 right) = d^2(d-2),d^k-3-(d-2)
\
&> left((d-1)^3+d^2right),d^k-3-(d-2)geq (d-1)^3,d^k-3+d^2-(d-2)
\
&>(d-1)^3,d^k-3-1geq (d-1)^k-1,,endalign$$
whence
$$|V|leq 1+d,left(frac(d-1)^k-1d-2right)<d^k,.$$
answered Jul 30 at 17:59
Batominovski
22.8k22777
Let $G(V,E)$ be a simple graph with radius at most $k$ and maximum degree at most $d$. Fix a center $uin V$ of $G$ (i.e., any path from $u$ to another vertex of $G$ is of length at most the radius of the graph). A vertex $vin V$ is of level $lin0,1,2,ldots,k$ if the shortest path from $u$ to $v$ is of length $l$. Write $N_l$ for the number of vertices of level $l$.
First, $N_0=1$. Thus, $N_1leq d$. We can easily seen that $$N_l+1leq (d-1),N_ltext for l=1,2,ldots,k-1,,$$ because a vertex of level $l+1$ must be joined by an edge to a vertex of level $l$, and each vertex of level $l$ can is adjacent to at most $d-1$ vertices of level $l+1$, having one edge connected to a vertex of level $l-1$. That is,
$$N_lleq d,(d-1)^l-1text for l=1,2,3,ldots,k,.$$
If $d>2$, then
$$beginalign
|V|&= sum_l=0^k,N_lleq 1+d,sum_l=1^k,(d-1)^l-1leq 1+kd(d-1)^k-1leq 1+kd^k,.
endalign$$
If $d=2$, then obviously, $N_lleq 2$ for all $l=1,2,ldots,k$, whence
$$|V|leq 1+2kleq 1+kd^k,.$$
If $d=1$, then the graph consist of at most $2$ vertices, so
$$|V|leq 2leq 1+kd^k,,$$
as $kgeq 1$.
The inequalities
$$|V|leq 1+d,sum_l=1^k,(d-1)^l-1=left{
beginarrayll
1+dleft(frac(d-1)^k-1(d-1)-1right),,&text for dneq 2,,\
1+2k,,&text for d=2,,endarrayright.$$
are sharp, and stronger than the original inequality $|V|leq 1+kd^k$. An example in each case should be easy to find. We can also show that $|V|< d^k$ for $dgeq 2$ and $kgeq 3$. The case $d=2$ is trivial. For $d>2$, we note that
$$beginalign(d-2),left(fracd^k-1dright)&> (d-2),left(d^k-1-1 right) = d^2(d-2),d^k-3-(d-2)
\
&> left((d-1)^3+d^2right),d^k-3-(d-2)geq (d-1)^3,d^k-3+d^2-(d-2)
\
&>(d-1)^3,d^k-3-1geq (d-1)^k-1,,endalign$$
whence
$$|V|leq 1+d,left(frac(d-1)^k-1d-2right)<d^k,.$$
answered Jul 30 at 17:59
Batominovski
22.8k22777
edited Jul 30 at 18:35
answered Jul 30 at 17:59
Batominovski
22.8k22777
answered Jul 30 at 17:59
Batominovski
22.8k22777
answered Jul 30 at 17:59
Batominovski
22.8k22777
22.8k22777
add a comment |Â
add a comment |Â
up vote
2
down vote
Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation
$$
1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+dots = 1+sum_i=0^k-1d(d-1)^i
$$
Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
add a comment |Â
up vote
2
down vote
Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation
$$
1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+dots = 1+sum_i=0^k-1d(d-1)^i
$$
Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation
$$
1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+dots = 1+sum_i=0^k-1d(d-1)^i
$$
Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
Let $v$ be a central vertex of the graph. This has at most $d$ neighbors. Each neighbor has at most $(d-1)$ other neighbors, for at most $d(d-1)$ total new vertices. Each of these neighbors has at most $(d-1)$ other neighbors, for $(d-1)^2d$ total new vertices. Continuing in this fashion, you get the summation
$$
1+ d + d(d-1) + d(d-1)^2 +d(d-1)^3+dots = 1+sum_i=0^k-1d(d-1)^i
$$
Note that the summation stops at $k$, because the distance from $v$ to any other vertex is at most $k$.
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
answered Jul 30 at 17:50
Mike Earnest
14.8k11644
14.8k11644
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
add a comment |Â
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
Thanks Mike Earnest
– Möbius
Jul 30 at 17:57
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%2f2867221%2fa-graph-g-of-radius-at-most-k-and-maximum-degree-at-most-d-has-no-more-tha%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