Fdtxjr

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$

0

$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

share|cite|improve this question

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 | 

0

$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

share|cite|improve this question

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

share|cite|improve this question

edited Mar 16 at 13:42

Roddy MacPhee

537118

asked Mar 16 at 11:00

Someone86Someone86

176

$endgroup$

share|cite|improve this question

edited Mar 16 at 13:42

Roddy MacPhee

537118

asked Mar 16 at 11:00

Someone86Someone86

176

share|cite|improve this question

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

asked Mar 16 at 11:00

Someone86Someone86

176

asked Mar 16 at 11:00

Someone86Someone86

176

1 Answer
1

active

oldest

votes

1

$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.

share|cite|improve this answer

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
);



);

draft saved

draft discarded

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

Name

Email

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

Name

Email

Required, but never shown

1

$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.

share|cite|improve this answer

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 | 

1

$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.

share|cite|improve this answer

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.

share|cite|improve this answer

answered Mar 16 at 14:56

Ross MillikanRoss Millikan

300k24200375

$endgroup$

share|cite|improve this answer

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