Mixing
If $G$ is simple with diameter two and maximum degree $|V(G)| - 2$, then $|E(G)| geq 2|V(G)| - 4$
This is my try:
Because the diameter of $G$ is two and have maximum degree the number of vertex: $|V(G)| - 2$, where $|V(G)|$ is the number of vertex, then the grade for any vertex in $G$ is greater than or equal to two. And since $sum delta(v_i) = |E(G)|$, where $delta(v_i)$ represents the grade of a vertex in $V(G)$ and $|E(G)|$ the number of edges in $G$, then $sum delta(v_i) geq 2(|V(G)| - 2) = 2|V(G)| - 4$.
graph-theory
asked Oct 31 '13 at 4:04
DavidDavid
19610
|
show 2 more comments
This is my try:
Because the diameter of $G$ is two and have maximum degree the number of vertex: $|V(G)| - 2$, where $|V(G)|$ is the number of vertex, then the grade for any vertex in $G$ is greater than or equal to two. And since $sum delta(v_i) = |E(G)|$, where $delta(v_i)$ represents the grade of a vertex in $V(G)$ and $|E(G)|$ the number of edges in $G$, then $sum delta(v_i) geq 2(|V(G)| - 2) = 2|V(G)| - 4$.
graph-theory
asked Oct 31 '13 at 4:04
DavidDavid
19610
1
$sum delta (v_i)$ counts each edge twice, that is, $sum delta (v_i)=2cdot |E(G)|$.
– DKal
Oct 31 '13 at 4:09
@bof I guess grade=degree=valency of a vertex, that is, the number of edges at the vertex.
– DKal
Oct 31 '13 at 4:15
@David do you need more help? or is it clear now?
– DKal
Oct 31 '13 at 4:17
Yes @DKal. I'm thinking how to repair my proof.
– David
Oct 31 '13 at 4:19
1
That proves that there is a vertex of degree at least $2$. A slightly more complicated argument will be needed to show that every vertex has degree at least $2$. You will have to use the assumption that the maximum degree is equal to $|V(G)|-2$. Diameter $2$ is not enough; the star $K_{1,n}$ has diameter $2$.
– bof
Oct 31 '13 at 4:35
|
show 2 more comments
This is my try:
Because the diameter of $G$ is two and have maximum degree the number of vertex: $|V(G)| - 2$, where $|V(G)|$ is the number of vertex, then the grade for any vertex in $G$ is greater than or equal to two. And since $sum delta(v_i) = |E(G)|$, where $delta(v_i)$ represents the grade of a vertex in $V(G)$ and $|E(G)|$ the number of edges in $G$, then $sum delta(v_i) geq 2(|V(G)| - 2) = 2|V(G)| - 4$.
graph-theory
asked Oct 31 '13 at 4:04
DavidDavid
19610
This is my try:
Because the diameter of $G$ is two and have maximum degree the number of vertex: $|V(G)| - 2$, where $|V(G)|$ is the number of vertex, then the grade for any vertex in $G$ is greater than or equal to two. And since $sum delta(v_i) = |E(G)|$, where $delta(v_i)$ represents the grade of a vertex in $V(G)$ and $|E(G)|$ the number of edges in $G$, then $sum delta(v_i) geq 2(|V(G)| - 2) = 2|V(G)| - 4$.
graph-theory
graph-theory
asked Oct 31 '13 at 4:04
DavidDavid
19610
asked Oct 31 '13 at 4:04
DavidDavid
19610
asked Oct 31 '13 at 4:04
DavidDavid
19610
asked Oct 31 '13 at 4:04
DavidDavid
19610
asked Oct 31 '13 at 4:04
DavidDavid
19610
19610
1
$sum delta (v_i)$ counts each edge twice, that is, $sum delta (v_i)=2cdot |E(G)|$.
– DKal
Oct 31 '13 at 4:09
@bof I guess grade=degree=valency of a vertex, that is, the number of edges at the vertex.
– DKal
Oct 31 '13 at 4:15
@David do you need more help? or is it clear now?
– DKal
Oct 31 '13 at 4:17
Yes @DKal. I'm thinking how to repair my proof.
– David
Oct 31 '13 at 4:19
1
That proves that there is a vertex of degree at least $2$. A slightly more complicated argument will be needed to show that every vertex has degree at least $2$. You will have to use the assumption that the maximum degree is equal to $|V(G)|-2$. Diameter $2$ is not enough; the star $K_{1,n}$ has diameter $2$.
– bof
Oct 31 '13 at 4:35
|
show 2 more comments
1
$sum delta (v_i)$ counts each edge twice, that is, $sum delta (v_i)=2cdot |E(G)|$.
– DKal
Oct 31 '13 at 4:09
@bof I guess grade=degree=valency of a vertex, that is, the number of edges at the vertex.
– DKal
Oct 31 '13 at 4:15
@David do you need more help? or is it clear now?
– DKal
Oct 31 '13 at 4:17
Yes @DKal. I'm thinking how to repair my proof.
– David
Oct 31 '13 at 4:19
1
That proves that there is a vertex of degree at least $2$. A slightly more complicated argument will be needed to show that every vertex has degree at least $2$. You will have to use the assumption that the maximum degree is equal to $|V(G)|-2$. Diameter $2$ is not enough; the star $K_{1,n}$ has diameter $2$.
– bof
Oct 31 '13 at 4:35
1
1
$sum delta (v_i)$ counts each edge twice, that is, $sum delta (v_i)=2cdot |E(G)|$.
– DKal
Oct 31 '13 at 4:09
$sum delta (v_i)$ counts each edge twice, that is, $sum delta (v_i)=2cdot |E(G)|$.
– DKal
Oct 31 '13 at 4:09
@bof I guess grade=degree=valency of a vertex, that is, the number of edges at the vertex.
– DKal
Oct 31 '13 at 4:15
@bof I guess grade=degree=valency of a vertex, that is, the number of edges at the vertex.
– DKal
Oct 31 '13 at 4:15
@David do you need more help? or is it clear now?
– DKal
Oct 31 '13 at 4:17
@David do you need more help? or is it clear now?
– DKal
Oct 31 '13 at 4:17
Yes @DKal. I'm thinking how to repair my proof.
– David
Oct 31 '13 at 4:19
Yes @DKal. I'm thinking how to repair my proof.
– David
Oct 31 '13 at 4:19
1
1
That proves that there is a vertex of degree at least $2$. A slightly more complicated argument will be needed to show that every vertex has degree at least $2$. You will have to use the assumption that the maximum degree is equal to $|V(G)|-2$. Diameter $2$ is not enough; the star $K_{1,n}$ has diameter $2$.
– bof
Oct 31 '13 at 4:35
That proves that there is a vertex of degree at least $2$. A slightly more complicated argument will be needed to show that every vertex has degree at least $2$. You will have to use the assumption that the maximum degree is equal to $|V(G)|-2$. Diameter $2$ is not enough; the star $K_{1,n}$ has diameter $2$.
– bof
Oct 31 '13 at 4:35
|
show 2 more comments
1 Answer
1
active
oldest
votes
Let $G$ be a graph of diameter $2$ and order $n=|V(G)|$, and suppose that $G$ has a vertex $v$ of degree $n-2$. It is easy to see that $G-v$ is a connected graph. [There is a vertex $u$ of $G-v$ which is not adjacent to $v$; every other vertex of $G-v$ is connected to $u$ by a path in $G$ of length at most $2$; since there is no edge $uv$, that path must be contained in $G-v$.] Since $G-v$ is a connected graph with $n-1$ vertices, it must have at least $n-2$ edges; added to the $n-2$ edges which are incident with $v$, this makes at least $2n-4$ edges in $G$.
Alternatively, without using the fact that a connected graph on $m$ vertices must have at least $m-1$ edges:
Let $N(x)$ denote the neighborhood of vertex $x$, i.e., the set of all vertices adjacent to $x$. Since $|N(v)|=n-2$, there is a unique vertex $uin V(G)setminus[{v}cup N(v)]$. Let $X= N(v)setminus N(u)$; so $|X|=n-2-|N(u)|$.Each vertex in $X$ is connected to $u$ by a path of length $2$, therefore, each vertex in $X$ is adjacent to some vertex in $N(u)$. Now there are $ n -2$ edges incident with $v$, and $|N(u)|$ edges incident with $u$, and at least $|X|$ edges joining vertices in $X$ to vertices in $N(u)$.Hence$$|E(G)|ge(n-2)+|N(u)|+|X|=(n-2)+|N(u)|+(n-2-|N(u)|)=2n-4.$$
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
answered Oct 31 '13 at 4:51
bofbof
5,3721218
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
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%2f546501%2fif-g-is-simple-with-diameter-two-and-maximum-degree-vg-2-then-eg%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
Let $G$ be a graph of diameter $2$ and order $n=|V(G)|$, and suppose that $G$ has a vertex $v$ of degree $n-2$. It is easy to see that $G-v$ is a connected graph. [There is a vertex $u$ of $G-v$ which is not adjacent to $v$; every other vertex of $G-v$ is connected to $u$ by a path in $G$ of length at most $2$; since there is no edge $uv$, that path must be contained in $G-v$.] Since $G-v$ is a connected graph with $n-1$ vertices, it must have at least $n-2$ edges; added to the $n-2$ edges which are incident with $v$, this makes at least $2n-4$ edges in $G$.
Alternatively, without using the fact that a connected graph on $m$ vertices must have at least $m-1$ edges:
Let $N(x)$ denote the neighborhood of vertex $x$, i.e., the set of all vertices adjacent to $x$. Since $|N(v)|=n-2$, there is a unique vertex $uin V(G)setminus[{v}cup N(v)]$. Let $X= N(v)setminus N(u)$; so $|X|=n-2-|N(u)|$.Each vertex in $X$ is connected to $u$ by a path of length $2$, therefore, each vertex in $X$ is adjacent to some vertex in $N(u)$. Now there are $ n -2$ edges incident with $v$, and $|N(u)|$ edges incident with $u$, and at least $|X|$ edges joining vertices in $X$ to vertices in $N(u)$.Hence$$|E(G)|ge(n-2)+|N(u)|+|X|=(n-2)+|N(u)|+(n-2-|N(u)|)=2n-4.$$
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
answered Oct 31 '13 at 4:51
bofbof
5,3721218
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
add a comment |
Let $G$ be a graph of diameter $2$ and order $n=|V(G)|$, and suppose that $G$ has a vertex $v$ of degree $n-2$. It is easy to see that $G-v$ is a connected graph. [There is a vertex $u$ of $G-v$ which is not adjacent to $v$; every other vertex of $G-v$ is connected to $u$ by a path in $G$ of length at most $2$; since there is no edge $uv$, that path must be contained in $G-v$.] Since $G-v$ is a connected graph with $n-1$ vertices, it must have at least $n-2$ edges; added to the $n-2$ edges which are incident with $v$, this makes at least $2n-4$ edges in $G$.
Alternatively, without using the fact that a connected graph on $m$ vertices must have at least $m-1$ edges:
Let $N(x)$ denote the neighborhood of vertex $x$, i.e., the set of all vertices adjacent to $x$. Since $|N(v)|=n-2$, there is a unique vertex $uin V(G)setminus[{v}cup N(v)]$. Let $X= N(v)setminus N(u)$; so $|X|=n-2-|N(u)|$.Each vertex in $X$ is connected to $u$ by a path of length $2$, therefore, each vertex in $X$ is adjacent to some vertex in $N(u)$. Now there are $ n -2$ edges incident with $v$, and $|N(u)|$ edges incident with $u$, and at least $|X|$ edges joining vertices in $X$ to vertices in $N(u)$.Hence$$|E(G)|ge(n-2)+|N(u)|+|X|=(n-2)+|N(u)|+(n-2-|N(u)|)=2n-4.$$
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
answered Oct 31 '13 at 4:51
bofbof
5,3721218
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
add a comment |
Let $G$ be a graph of diameter $2$ and order $n=|V(G)|$, and suppose that $G$ has a vertex $v$ of degree $n-2$. It is easy to see that $G-v$ is a connected graph. [There is a vertex $u$ of $G-v$ which is not adjacent to $v$; every other vertex of $G-v$ is connected to $u$ by a path in $G$ of length at most $2$; since there is no edge $uv$, that path must be contained in $G-v$.] Since $G-v$ is a connected graph with $n-1$ vertices, it must have at least $n-2$ edges; added to the $n-2$ edges which are incident with $v$, this makes at least $2n-4$ edges in $G$.
Alternatively, without using the fact that a connected graph on $m$ vertices must have at least $m-1$ edges:
Let $N(x)$ denote the neighborhood of vertex $x$, i.e., the set of all vertices adjacent to $x$. Since $|N(v)|=n-2$, there is a unique vertex $uin V(G)setminus[{v}cup N(v)]$. Let $X= N(v)setminus N(u)$; so $|X|=n-2-|N(u)|$.Each vertex in $X$ is connected to $u$ by a path of length $2$, therefore, each vertex in $X$ is adjacent to some vertex in $N(u)$. Now there are $ n -2$ edges incident with $v$, and $|N(u)|$ edges incident with $u$, and at least $|X|$ edges joining vertices in $X$ to vertices in $N(u)$.Hence$$|E(G)|ge(n-2)+|N(u)|+|X|=(n-2)+|N(u)|+(n-2-|N(u)|)=2n-4.$$
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
answered Oct 31 '13 at 4:51
bofbof
5,3721218
Let $G$ be a graph of diameter $2$ and order $n=|V(G)|$, and suppose that $G$ has a vertex $v$ of degree $n-2$. It is easy to see that $G-v$ is a connected graph. [There is a vertex $u$ of $G-v$ which is not adjacent to $v$; every other vertex of $G-v$ is connected to $u$ by a path in $G$ of length at most $2$; since there is no edge $uv$, that path must be contained in $G-v$.] Since $G-v$ is a connected graph with $n-1$ vertices, it must have at least $n-2$ edges; added to the $n-2$ edges which are incident with $v$, this makes at least $2n-4$ edges in $G$.
Alternatively, without using the fact that a connected graph on $m$ vertices must have at least $m-1$ edges:
Let $N(x)$ denote the neighborhood of vertex $x$, i.e., the set of all vertices adjacent to $x$. Since $|N(v)|=n-2$, there is a unique vertex $uin V(G)setminus[{v}cup N(v)]$. Let $X= N(v)setminus N(u)$; so $|X|=n-2-|N(u)|$.Each vertex in $X$ is connected to $u$ by a path of length $2$, therefore, each vertex in $X$ is adjacent to some vertex in $N(u)$. Now there are $ n -2$ edges incident with $v$, and $|N(u)|$ edges incident with $u$, and at least $|X|$ edges joining vertices in $X$ to vertices in $N(u)$.Hence$$|E(G)|ge(n-2)+|N(u)|+|X|=(n-2)+|N(u)|+(n-2-|N(u)|)=2n-4.$$
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
answered Oct 31 '13 at 4:51
bofbof
5,3721218
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
edited Nov 21 '18 at 17:35
Sri Krishna Sahoo
600217
600217
answered Oct 31 '13 at 4:51
bofbof
5,3721218
answered Oct 31 '13 at 4:51
bofbof
5,3721218
answered Oct 31 '13 at 4:51
bofbof
5,3721218
5,3721218
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
add a comment |
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
This exercise is in my book (Bondy & Morty) before cycles, i.e, before connectivity.
– David
Oct 31 '13 at 5:00
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
First edition, page 14. @bof
– David
Oct 31 '13 at 5:09
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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2f546501%2fif-g-is-simple-with-diameter-two-and-maximum-degree-vg-2-then-eg%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
1
$sum delta (v_i)$ counts each edge twice, that is, $sum delta (v_i)=2cdot |E(G)|$.
– DKal
Oct 31 '13 at 4:09
@bof I guess grade=degree=valency of a vertex, that is, the number of edges at the vertex.
– DKal
Oct 31 '13 at 4:15
@David do you need more help? or is it clear now?
– DKal
Oct 31 '13 at 4:17
Yes @DKal. I'm thinking how to repair my proof.
– David
Oct 31 '13 at 4:19
1
That proves that there is a vertex of degree at least $2$. A slightly more complicated argument will be needed to show that every vertex has degree at least $2$. You will have to use the assumption that the maximum degree is equal to $|V(G)|-2$. Diameter $2$ is not enough; the star $K_{1,n}$ has diameter $2$.
– bof
Oct 31 '13 at 4:35