Prove that there exists a graph with these points such that G is connected
up vote
0
down vote
favorite
Let us have $n geq 3$ points in a square whose side length is $1$. Prove that there exists a graph with these points such that $G$ is connected, and
$$sum_{{v_i,v_j} in E(G)}{|v_i - v_j|} leq 10sqrt{n}$$
Prove also the $10$ in the inequality can't be replaced with $1$.
I think I should use Erdös-Renyi random graph model to prove the existence of a connected graph. In that model, if an edge appears with probability $p$, then, for example, a particular connected graph with $n-1$ edges appear with $p^{n-1}(1-p)^{binom{n}{2} - (n - 1)}$. Is this enough to show a connected graph exists since this probability should be greater than zero? Regardless of this, I found proofs showing that the expected distance between two points picked on a unit square is around $0.52$, but I think that is not useful. Should I look for the expected value of the total length of $n$ points maybe?
real-analysis probability-theory proof-verification combinations
asked 9 hours ago
user2694307
195210
add a comment |
up vote
0
down vote
favorite
Let us have $n geq 3$ points in a square whose side length is $1$. Prove that there exists a graph with these points such that $G$ is connected, and
$$sum_{{v_i,v_j} in E(G)}{|v_i - v_j|} leq 10sqrt{n}$$
Prove also the $10$ in the inequality can't be replaced with $1$.
I think I should use Erdös-Renyi random graph model to prove the existence of a connected graph. In that model, if an edge appears with probability $p$, then, for example, a particular connected graph with $n-1$ edges appear with $p^{n-1}(1-p)^{binom{n}{2} - (n - 1)}$. Is this enough to show a connected graph exists since this probability should be greater than zero? Regardless of this, I found proofs showing that the expected distance between two points picked on a unit square is around $0.52$, but I think that is not useful. Should I look for the expected value of the total length of $n$ points maybe?
real-analysis probability-theory proof-verification combinations
asked 9 hours ago
user2694307
195210
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Let us have $n geq 3$ points in a square whose side length is $1$. Prove that there exists a graph with these points such that $G$ is connected, and
$$sum_{{v_i,v_j} in E(G)}{|v_i - v_j|} leq 10sqrt{n}$$
Prove also the $10$ in the inequality can't be replaced with $1$.
I think I should use Erdös-Renyi random graph model to prove the existence of a connected graph. In that model, if an edge appears with probability $p$, then, for example, a particular connected graph with $n-1$ edges appear with $p^{n-1}(1-p)^{binom{n}{2} - (n - 1)}$. Is this enough to show a connected graph exists since this probability should be greater than zero? Regardless of this, I found proofs showing that the expected distance between two points picked on a unit square is around $0.52$, but I think that is not useful. Should I look for the expected value of the total length of $n$ points maybe?
real-analysis probability-theory proof-verification combinations
asked 9 hours ago
user2694307
195210
Let us have $n geq 3$ points in a square whose side length is $1$. Prove that there exists a graph with these points such that $G$ is connected, and
$$sum_{{v_i,v_j} in E(G)}{|v_i - v_j|} leq 10sqrt{n}$$
Prove also the $10$ in the inequality can't be replaced with $1$.
I think I should use Erdös-Renyi random graph model to prove the existence of a connected graph. In that model, if an edge appears with probability $p$, then, for example, a particular connected graph with $n-1$ edges appear with $p^{n-1}(1-p)^{binom{n}{2} - (n - 1)}$. Is this enough to show a connected graph exists since this probability should be greater than zero? Regardless of this, I found proofs showing that the expected distance between two points picked on a unit square is around $0.52$, but I think that is not useful. Should I look for the expected value of the total length of $n$ points maybe?
real-analysis probability-theory proof-verification combinations
real-analysis probability-theory proof-verification combinations
asked 9 hours ago
user2694307
195210
asked 9 hours ago
user2694307
195210
edited 1 hour ago
asked 9 hours ago
user2694307
195210
asked 9 hours ago
user2694307
195210
asked 9 hours ago
user2694307
195210
195210
add a comment |
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%2f3004319%2fprove-that-there-exists-a-graph-with-these-points-such-that-g-is-connected%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
