Large graph connectivity implies both many and few edges?
$begingroup$
Let $G$ be a simple graph with $v$ vertices, $e$ edges, and edge connectivity $c$. Since $2e / v$ is the average degree of all vertices, we must have $c leq 2e / v$, since there is some vertex with degree $leq 2e / v$.
This relation is simple. For a fixed number of vertices, you need more edges to be more connected. However, it implies another inequality that seems to say the exact opposite.
The inequality is equivalent to $v leq 2e / c$. Given an upper bound for $v$, we immediately obtain an upper bound for $e$, namely $$e leq frac{1}{2} frac{2e}{c} left( frac{2e}{c} - 1 right).$$ Since $e$ is always bounded by $D = v(v - 1) / 2$, we also obtain $$e leq frac{1}{2} frac{D}{c} left( frac{D}{c} - 1 right).$$
Now this says that for a fixed number of vertices, you need fewer edges as connectivity grows! This seems to contradict my interpretation of the first inequality. Have I made a mistake somewhere, or am I interpreting something wrong?
proof-verification inequality graph-theory
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
$endgroup$
add a comment |
$begingroup$
Let $G$ be a simple graph with $v$ vertices, $e$ edges, and edge connectivity $c$. Since $2e / v$ is the average degree of all vertices, we must have $c leq 2e / v$, since there is some vertex with degree $leq 2e / v$.
This relation is simple. For a fixed number of vertices, you need more edges to be more connected. However, it implies another inequality that seems to say the exact opposite.
The inequality is equivalent to $v leq 2e / c$. Given an upper bound for $v$, we immediately obtain an upper bound for $e$, namely $$e leq frac{1}{2} frac{2e}{c} left( frac{2e}{c} - 1 right).$$ Since $e$ is always bounded by $D = v(v - 1) / 2$, we also obtain $$e leq frac{1}{2} frac{D}{c} left( frac{D}{c} - 1 right).$$
Now this says that for a fixed number of vertices, you need fewer edges as connectivity grows! This seems to contradict my interpretation of the first inequality. Have I made a mistake somewhere, or am I interpreting something wrong?
proof-verification inequality graph-theory
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
$endgroup$
add a comment |
$begingroup$
Let $G$ be a simple graph with $v$ vertices, $e$ edges, and edge connectivity $c$. Since $2e / v$ is the average degree of all vertices, we must have $c leq 2e / v$, since there is some vertex with degree $leq 2e / v$.
This relation is simple. For a fixed number of vertices, you need more edges to be more connected. However, it implies another inequality that seems to say the exact opposite.
The inequality is equivalent to $v leq 2e / c$. Given an upper bound for $v$, we immediately obtain an upper bound for $e$, namely $$e leq frac{1}{2} frac{2e}{c} left( frac{2e}{c} - 1 right).$$ Since $e$ is always bounded by $D = v(v - 1) / 2$, we also obtain $$e leq frac{1}{2} frac{D}{c} left( frac{D}{c} - 1 right).$$
Now this says that for a fixed number of vertices, you need fewer edges as connectivity grows! This seems to contradict my interpretation of the first inequality. Have I made a mistake somewhere, or am I interpreting something wrong?
proof-verification inequality graph-theory
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
$endgroup$
Let $G$ be a simple graph with $v$ vertices, $e$ edges, and edge connectivity $c$. Since $2e / v$ is the average degree of all vertices, we must have $c leq 2e / v$, since there is some vertex with degree $leq 2e / v$.
This relation is simple. For a fixed number of vertices, you need more edges to be more connected. However, it implies another inequality that seems to say the exact opposite.
The inequality is equivalent to $v leq 2e / c$. Given an upper bound for $v$, we immediately obtain an upper bound for $e$, namely $$e leq frac{1}{2} frac{2e}{c} left( frac{2e}{c} - 1 right).$$ Since $e$ is always bounded by $D = v(v - 1) / 2$, we also obtain $$e leq frac{1}{2} frac{D}{c} left( frac{D}{c} - 1 right).$$
Now this says that for a fixed number of vertices, you need fewer edges as connectivity grows! This seems to contradict my interpretation of the first inequality. Have I made a mistake somewhere, or am I interpreting something wrong?
proof-verification inequality graph-theory
proof-verification inequality graph-theory
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
asked Jan 6 at 19:21
rwboglrwbogl
1,027617
1,027617
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Your last inequality is trivial though, even for $c = n-1$ (and you are missing a couple of factors of 2 on the RHS). Your last inequality with the missing factors of 2 put into the RHS (and $c = n-1$) yields $e le frac{n(n-1)}{2}$.
answered Jan 6 at 19:30
MikeMike
4,461512
$endgroup$
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
1
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
1
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
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%2f3064300%2flarge-graph-connectivity-implies-both-many-and-few-edges%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Your last inequality is trivial though, even for $c = n-1$ (and you are missing a couple of factors of 2 on the RHS). Your last inequality with the missing factors of 2 put into the RHS (and $c = n-1$) yields $e le frac{n(n-1)}{2}$.
answered Jan 6 at 19:30
MikeMike
4,461512
$endgroup$
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
1
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
1
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
add a comment |
$begingroup$
Your last inequality is trivial though, even for $c = n-1$ (and you are missing a couple of factors of 2 on the RHS). Your last inequality with the missing factors of 2 put into the RHS (and $c = n-1$) yields $e le frac{n(n-1)}{2}$.
answered Jan 6 at 19:30
MikeMike
4,461512
$endgroup$
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
1
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
1
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
add a comment |
$begingroup$
Your last inequality is trivial though, even for $c = n-1$ (and you are missing a couple of factors of 2 on the RHS). Your last inequality with the missing factors of 2 put into the RHS (and $c = n-1$) yields $e le frac{n(n-1)}{2}$.
answered Jan 6 at 19:30
MikeMike
4,461512
$endgroup$
Your last inequality is trivial though, even for $c = n-1$ (and you are missing a couple of factors of 2 on the RHS). Your last inequality with the missing factors of 2 put into the RHS (and $c = n-1$) yields $e le frac{n(n-1)}{2}$.
answered Jan 6 at 19:30
MikeMike
4,461512
answered Jan 6 at 19:30
MikeMike
4,461512
answered Jan 6 at 19:30
MikeMike
4,461512
answered Jan 6 at 19:30
MikeMike
4,461512
4,461512
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
1
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
1
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
add a comment |
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
1
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
1
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
$begingroup$
Why can we take $c = n - 1$ and say that the whole thing is trivial? Couldn't we have $c > n - 1$?
$endgroup$
– rwbogl
Jan 6 at 19:45
1
1
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
$begingroup$
No $c$ cannot be any larger than $n-1$, as each vertex in an $n$-vertex (simple) graph has degree at most $n-1$, and cutting those $n-1$ edges disconnects the graph.
$endgroup$
– Mike
Jan 6 at 19:49
1
1
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
$begingroup$
Ah, of course. Silly thing to overlook. Thanks for clarifying!
$endgroup$
– rwbogl
Jan 6 at 19:51
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
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%2f3064300%2flarge-graph-connectivity-implies-both-many-and-few-edges%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
