Number of Triangles in a graph with $n$ vertices and $m$ edgesMaximum number of edges in a non-Hamiltonian graphgraph theory: upper bound on edge number, given number of vertices andHow to prove that for any graph on $8$ nodes with exactly $17$ edges has at least $4$ triangles.How many triangles may a connected simple graph with m edges have at most?Independence Number of A Given GraphNumber of vertices of a complete graph with $n$ edgesInductively the number of edges for a connected graphMinimum Edges per Vertex in a Graph with a Given Number of Edges and VerticesA connected graph with n vertices has at least n-1 edgesUpper bounds for number of $3$-flags in a $(2k, k^2)$-graph $G$
How do I extrude a face to a single vertex
Query about absorption line spectra
How do you respond to a colleague from another team when they're wrongly expecting that you'll help them?
Is camera lens focus an exact point or a range?
Using a siddur to Daven from in a seforim store
How to color a curve
In Star Trek IV, why did the Bounty go back to a time when whales are already rare?
THT: What is a squared annular “ring”?
Bob has never been a M before
Why did the EU agree to delay the Brexit deadline?
Folder comparison
Why is Arduino resetting while driving motors?
Why does Async/Await work properly when the loop is inside the async function and not the other way around?
Open a doc from terminal, but not by its name
What does the Rambam mean when he says that the planets have souls?
A social experiment. What is the worst that can happen?
Drawing ramified coverings with tikz
A Permanent Norse Presence in America
How do ground effect vehicles perform turns?
Transformation of random variables and joint distributions
Java - What do constructor type arguments mean when placed *before* the type?
Is possible to search in vim history?
On a tidally locked planet, would time be quantized?
Does having a TSA Pre-Check member in your flight reservation increase the chances that everyone gets Pre-Check?
Number of Triangles in a graph with $n$ vertices and $m$ edges
Maximum number of edges in a non-Hamiltonian graphgraph theory: upper bound on edge number, given number of vertices andHow to prove that for any graph on $8$ nodes with exactly $17$ edges has at least $4$ triangles.How many triangles may a connected simple graph with m edges have at most?Independence Number of A Given GraphNumber of vertices of a complete graph with $n$ edgesInductively the number of edges for a connected graphMinimum Edges per Vertex in a Graph with a Given Number of Edges and VerticesA connected graph with n vertices has at least n-1 edgesUpper bounds for number of $3$-flags in a $(2k, k^2)$-graph $G$
$begingroup$
One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $dfrac4m3n(m-dfracn^24)$. I was wondering, about the best lowest bound of this, and the best upper bound of this ( is the best upper bound truly, the number of triangles formed in the complete graph , i.e $ Delta(G) choose 3$ ?
inequality graph-theory triangles algebraic-graph-theory
edited Mar 16 at 13:42
Roddy MacPhee
537118
asked Mar 16 at 11:00
Someone86Someone86
176
$endgroup$
add a comment |
$begingroup$
One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $dfrac4m3n(m-dfracn^24)$. I was wondering, about the best lowest bound of this, and the best upper bound of this ( is the best upper bound truly, the number of triangles formed in the complete graph , i.e $ Delta(G) choose 3$ ?
inequality graph-theory triangles algebraic-graph-theory
edited Mar 16 at 13:42
Roddy MacPhee
537118
asked Mar 16 at 11:00
Someone86Someone86
176
$endgroup$
$begingroup$
Are you demanding the graph be simple? If not, do you count three loops at the same vertex as a triangle?
$endgroup$
– Ross Millikan
Mar 16 at 14:09
$begingroup$
Yes, I suppose its simple, my knowledge is limited at the moment around simple graphs.
$endgroup$
– Someone86
Mar 16 at 14:41
add a comment |
$begingroup$
One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $dfrac4m3n(m-dfracn^24)$. I was wondering, about the best lowest bound of this, and the best upper bound of this ( is the best upper bound truly, the number of triangles formed in the complete graph , i.e $ Delta(G) choose 3$ ?
inequality graph-theory triangles algebraic-graph-theory
edited Mar 16 at 13:42
Roddy MacPhee
537118
asked Mar 16 at 11:00
Someone86Someone86
176
$endgroup$
One can show, that a Graph with at least $n$ vertices and $m$ edges, has at least $dfrac4m3n(m-dfracn^24)$. I was wondering, about the best lowest bound of this, and the best upper bound of this ( is the best upper bound truly, the number of triangles formed in the complete graph , i.e $ Delta(G) choose 3$ ?
inequality graph-theory triangles algebraic-graph-theory
inequality graph-theory triangles algebraic-graph-theory
edited Mar 16 at 13:42
Roddy MacPhee
537118
asked Mar 16 at 11:00
Someone86Someone86
176
edited Mar 16 at 13:42
Roddy MacPhee
537118
asked Mar 16 at 11:00
Someone86Someone86
176
edited Mar 16 at 13:42
Roddy MacPhee
537118
edited Mar 16 at 13:42
Roddy MacPhee
537118
edited Mar 16 at 13:42
Roddy MacPhee
537118
537118
asked Mar 16 at 11:00
Someone86Someone86
176
asked Mar 16 at 11:00
Someone86Someone86
176
asked Mar 16 at 11:00
Someone86Someone86
176
176
$begingroup$
Are you demanding the graph be simple? If not, do you count three loops at the same vertex as a triangle?
$endgroup$
– Ross Millikan
Mar 16 at 14:09
$begingroup$
Yes, I suppose its simple, my knowledge is limited at the moment around simple graphs.
$endgroup$
– Someone86
Mar 16 at 14:41
add a comment |
$begingroup$
Are you demanding the graph be simple? If not, do you count three loops at the same vertex as a triangle?
$endgroup$
– Ross Millikan
Mar 16 at 14:09
$begingroup$
Yes, I suppose its simple, my knowledge is limited at the moment around simple graphs.
$endgroup$
– Someone86
Mar 16 at 14:41
$begingroup$
Are you demanding the graph be simple? If not, do you count three loops at the same vertex as a triangle?
$endgroup$
– Ross Millikan
Mar 16 at 14:09
$begingroup$
Are you demanding the graph be simple? If not, do you count three loops at the same vertex as a triangle?
$endgroup$
– Ross Millikan
Mar 16 at 14:09
$begingroup$
Yes, I suppose its simple, my knowledge is limited at the moment around simple graphs.
$endgroup$
– Someone86
Mar 16 at 14:41
$begingroup$
Yes, I suppose its simple, my knowledge is limited at the moment around simple graphs.
$endgroup$
– Someone86
Mar 16 at 14:41
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
An upper bound is $frac 13m choose 2=frac m(m-1)6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times. This is achieved in a complete graph. To have a complete graph with $m$ edges requires that $m$ be a triangular number, that $m=frac 12n(n-1)$. The number of triangles is then $n choose 3$ as you say.
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
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%2f3150289%2fnumber-of-triangles-in-a-graph-with-n-vertices-and-m-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$
An upper bound is $frac 13m choose 2=frac m(m-1)6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times. This is achieved in a complete graph. To have a complete graph with $m$ edges requires that $m$ be a triangular number, that $m=frac 12n(n-1)$. The number of triangles is then $n choose 3$ as you say.
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
add a comment |
$begingroup$
An upper bound is $frac 13m choose 2=frac m(m-1)6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times. This is achieved in a complete graph. To have a complete graph with $m$ edges requires that $m$ be a triangular number, that $m=frac 12n(n-1)$. The number of triangles is then $n choose 3$ as you say.
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
$endgroup$
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
add a comment |
$begingroup$
An upper bound is $frac 13m choose 2=frac m(m-1)6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times. This is achieved in a complete graph. To have a complete graph with $m$ edges requires that $m$ be a triangular number, that $m=frac 12n(n-1)$. The number of triangles is then $n choose 3$ as you say.
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
$endgroup$
An upper bound is $frac 13m choose 2=frac m(m-1)6$ because at the most you can choose any two edges and have one triangle, then each triangle gets counted $3$ times. This is achieved in a complete graph. To have a complete graph with $m$ edges requires that $m$ be a triangular number, that $m=frac 12n(n-1)$. The number of triangles is then $n choose 3$ as you say.
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
answered Mar 16 at 14:56
Ross MillikanRoss Millikan
300k24200375
300k24200375
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
add a comment |
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
Thank you for the answer, what about the best lowest bound?
$endgroup$
– Someone86
Mar 16 at 16:31
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
One lower bound is that the complete bipartite graph on $n$ vertices has $frac n^24$ edges and no triangles. This supports the $(m-frac n^24)$ factor in your expression. Now, if my image is correct, each edge you add adds $frac n2$ triangles, so this approach gives $frac n2(m-frac n^24)$ triangles. I do not know if there is a way to have fewer.
$endgroup$
– Ross Millikan
Mar 16 at 21:08
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I see yes..can you give more details about how you got the result? I have a more complex solution on my mind and yours seems more elegant..
$endgroup$
– Someone86
Mar 17 at 0:11
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
$begingroup$
I just imagined the complete bipartite graph. You split the vertices into two groups of $frac n2$ and connect all the vertices of one group to all the vertices of the other. There are no triangles. Now if you add an edge, you have to add it within a group. The next sentence is a little wrong, but it is how I was thinking. All the triangles containing that edge have one vertex from the other group, so each time you add an edge you add $frac n2$. This is true until you add more than $frac n4$ edges, at which point you cannot avoid a triangle within the one side.
$endgroup$
– Ross Millikan
Mar 17 at 2:08
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%2f3150289%2fnumber-of-triangles-in-a-graph-with-n-vertices-and-m-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
$begingroup$
Are you demanding the graph be simple? If not, do you count three loops at the same vertex as a triangle?
$endgroup$
– Ross Millikan
Mar 16 at 14:09
$begingroup$
Yes, I suppose its simple, my knowledge is limited at the moment around simple graphs.
$endgroup$
– Someone86
Mar 16 at 14:41