A lower bound for the number of triangles that contain a particular edge
$begingroup$
If $u leftrightarrow v$ in a graph $G$, prove that $uv$ belongs to at least $d(u) + d(v) − n(G)$ triangles in $G$, where $n(G)=$ number of vertices in $G$.
In this question, I tried a lot. I know we are supposed to start with $2$ vertices and check the vertices they are adjacent to, but I'm unable to write the entire solution. Please help.
graph-theory
edited Dec 17 '18 at 13:09
amWhy
1
$endgroup$
add a comment |
$begingroup$
If $u leftrightarrow v$ in a graph $G$, prove that $uv$ belongs to at least $d(u) + d(v) − n(G)$ triangles in $G$, where $n(G)=$ number of vertices in $G$.
In this question, I tried a lot. I know we are supposed to start with $2$ vertices and check the vertices they are adjacent to, but I'm unable to write the entire solution. Please help.
graph-theory
edited Dec 17 '18 at 13:09
amWhy
1
$endgroup$
$begingroup$
What is $n(G)$?
$endgroup$
– Robert Z
Dec 17 '18 at 12:54
$begingroup$
Number of vertices in G
$endgroup$
– user626673
Dec 17 '18 at 12:59
add a comment |
$begingroup$
If $u leftrightarrow v$ in a graph $G$, prove that $uv$ belongs to at least $d(u) + d(v) − n(G)$ triangles in $G$, where $n(G)=$ number of vertices in $G$.
In this question, I tried a lot. I know we are supposed to start with $2$ vertices and check the vertices they are adjacent to, but I'm unable to write the entire solution. Please help.
graph-theory
edited Dec 17 '18 at 13:09
amWhy
1
$endgroup$
If $u leftrightarrow v$ in a graph $G$, prove that $uv$ belongs to at least $d(u) + d(v) − n(G)$ triangles in $G$, where $n(G)=$ number of vertices in $G$.
In this question, I tried a lot. I know we are supposed to start with $2$ vertices and check the vertices they are adjacent to, but I'm unable to write the entire solution. Please help.
graph-theory
graph-theory
edited Dec 17 '18 at 13:09
amWhy
1
edited Dec 17 '18 at 13:09
amWhy
1
edited Dec 17 '18 at 13:09
amWhy
1
edited Dec 17 '18 at 13:09
amWhy
1
edited Dec 17 '18 at 13:09
amWhy
1
1
asked Dec 17 '18 at 12:51
user626673
$begingroup$
What is $n(G)$?
$endgroup$
– Robert Z
Dec 17 '18 at 12:54
$begingroup$
Number of vertices in G
$endgroup$
– user626673
Dec 17 '18 at 12:59
add a comment |
$begingroup$
What is $n(G)$?
$endgroup$
– Robert Z
Dec 17 '18 at 12:54
$begingroup$
Number of vertices in G
$endgroup$
– user626673
Dec 17 '18 at 12:59
$begingroup$
What is $n(G)$?
$endgroup$
– Robert Z
Dec 17 '18 at 12:54
$begingroup$
What is $n(G)$?
$endgroup$
– Robert Z
Dec 17 '18 at 12:54
$begingroup$
Number of vertices in G
$endgroup$
– user626673
Dec 17 '18 at 12:59
$begingroup$
Number of vertices in G
$endgroup$
– user626673
Dec 17 '18 at 12:59
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
Working in the direction you mentioned, let the set of vertices adj. to $u$ be $A$ and to $v$ be $B$. The set of vertices adjacent to both $u$ & $v$ $=Acap B$. Note that
$$|Acap B|=|A|+|B|-|Acup B|$$
$$|A|=d(u), |B|=d(v) quad and quad|Acup B|leq n(G)$$
Also, $|Acap B|=$the no. of triangles asked since they'll formed with the vertices common to $u$ and $v$.
So, $$|Acap B|=|A|+|B|-|Acup B|geq d(u)+d(v)-n(G)$$
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
$endgroup$
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
1
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
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%2f3043897%2fa-lower-bound-for-the-number-of-triangles-that-contain-a-particular-edge%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$
Working in the direction you mentioned, let the set of vertices adj. to $u$ be $A$ and to $v$ be $B$. The set of vertices adjacent to both $u$ & $v$ $=Acap B$. Note that
$$|Acap B|=|A|+|B|-|Acup B|$$
$$|A|=d(u), |B|=d(v) quad and quad|Acup B|leq n(G)$$
Also, $|Acap B|=$the no. of triangles asked since they'll formed with the vertices common to $u$ and $v$.
So, $$|Acap B|=|A|+|B|-|Acup B|geq d(u)+d(v)-n(G)$$
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
$endgroup$
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
1
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
add a comment |
$begingroup$
Working in the direction you mentioned, let the set of vertices adj. to $u$ be $A$ and to $v$ be $B$. The set of vertices adjacent to both $u$ & $v$ $=Acap B$. Note that
$$|Acap B|=|A|+|B|-|Acup B|$$
$$|A|=d(u), |B|=d(v) quad and quad|Acup B|leq n(G)$$
Also, $|Acap B|=$the no. of triangles asked since they'll formed with the vertices common to $u$ and $v$.
So, $$|Acap B|=|A|+|B|-|Acup B|geq d(u)+d(v)-n(G)$$
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
$endgroup$
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
1
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
add a comment |
$begingroup$
Working in the direction you mentioned, let the set of vertices adj. to $u$ be $A$ and to $v$ be $B$. The set of vertices adjacent to both $u$ & $v$ $=Acap B$. Note that
$$|Acap B|=|A|+|B|-|Acup B|$$
$$|A|=d(u), |B|=d(v) quad and quad|Acup B|leq n(G)$$
Also, $|Acap B|=$the no. of triangles asked since they'll formed with the vertices common to $u$ and $v$.
So, $$|Acap B|=|A|+|B|-|Acup B|geq d(u)+d(v)-n(G)$$
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
$endgroup$
Working in the direction you mentioned, let the set of vertices adj. to $u$ be $A$ and to $v$ be $B$. The set of vertices adjacent to both $u$ & $v$ $=Acap B$. Note that
$$|Acap B|=|A|+|B|-|Acup B|$$
$$|A|=d(u), |B|=d(v) quad and quad|Acup B|leq n(G)$$
Also, $|Acap B|=$the no. of triangles asked since they'll formed with the vertices common to $u$ and $v$.
So, $$|Acap B|=|A|+|B|-|Acup B|geq d(u)+d(v)-n(G)$$
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
answered Dec 17 '18 at 13:03
Ankit KumarAnkit Kumar
1,352219
1,352219
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
1
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
add a comment |
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
1
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
$begingroup$
Thank you, it was a very clear solution. However, my question was recently edited to be "A lower bound for the number of triangles that contain a particular edge ". I'm just wondering, is there any upper bound to it to?
$endgroup$
– user626673
Dec 17 '18 at 13:10
1
1
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
$begingroup$
For that, we'll have to minimise $|A cup B|$, which is the no. of vertices common to u or v, which is $d(u)+d(v)$, if I'm not wrong. You can get the corresponding upper bound then.
$endgroup$
– Ankit Kumar
Dec 17 '18 at 13:42
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%2f3043897%2fa-lower-bound-for-the-number-of-triangles-that-contain-a-particular-edge%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
$begingroup$
What is $n(G)$?
$endgroup$
– Robert Z
Dec 17 '18 at 12:54
$begingroup$
Number of vertices in G
$endgroup$
– user626673
Dec 17 '18 at 12:59