Fdtxjr

Why doesn't Newton's third law mean a person bounces back to where they started when they hit the ground?

LaTeX closing $ signs makes cursor jump

Arthur Somervell: 1000 Exercises - Meaning of this notation

The use of multiple foreign keys on same column in SQL Server

Has the BBC provided arguments for saying Brexit being cancelled is unlikely?

Finding angle with pure Geometry.

How could an uplifted falcon's brain work?

What do you call a Matrix-like slowdown and camera movement effect?

I’m planning on buying a laser printer but concerned about the life cycle of toner in the machine

What would happen to a modern skyscraper if it rains micro blackholes?

Minkowski space

Show that if two triangles built on parallel lines, with equal bases have the same perimeter only if they are congruent.

Why are electrically insulating heatsinks so rare? Is it just cost?

Theorems that impeded progress

How to write a macro that is braces sensitive?

How did the USSR manage to innovate in an environment characterized by government censorship and high bureaucracy?

tikz: show 0 at the axis origin

Adding span tags within wp_list_pages list items

Writing rule stating superpower from different root cause is bad writing

How can bays and straits be determined in a procedurally generated map?

Today is the Center

Why did Neo believe he could trust the machine when he asked for peace?

Why can't I see bouncing of a switch on an oscilloscope?

What's the output of a record cartridge playing an out-of-speed record

Triangle free graph with $n$ vertices and maximum degree $k$ has at most $k(n-k)$ edges.

Graph theory Problem 'of the court'A graph with 20 edges has 5 vertices of degree 5 with the rest of degree 4. How many vertices of each degree does it have?Prove that a graph $G$ is a forest if and only if every induced subgraph of $G$ contain a vertex of degree at most $1$existence of a spanning subgraph with min degree $delta$ and at most $(n-1)delta$ edgesLet *G* be a simple graph having no isolated vertex and no induced subgraph with exactly 2 edges.Does a directed edge on graph going both ways contribute 2 to out-degree and in-degree?A graph with an equal number of edges and vertices contains a cycle as a subgraphFinding the largest triangle-free induced subgraph in a given simple graph $G$ is NP-Complete.Find the average of all of the degrees in a graph containing $8$ vertices and $21$ edges.Let $G$ be a graph with n vertices and n-1 edges.How can I get maximum number of vertices if I already know edges

1

2

$begingroup$

Having a graph $G$ which is simple and non-directed with $n$ vertices and max degree of a vertex $k$. Then show if it does not contain $K_3$ as induced subgraph then that proves $|E(G)|le (n-k)k$

So,having to find an upper limit to the number of edges.
My thoughts so far are:

1)If it does not contain an induced subgraph of $K_3$ then it does not have any kind of bigger $K$ and then the degree of $k$ is $2$.

Extra thought(not complete):Having a vertex ν that is $k(=2)$ degree then compute the sum of degrees $V(G)-N(v)$. [$N(ν)$ is neighbourhood of $v$].I need some analysis if correct to this last statement.

combinatorics graph-theory

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

27k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Note that this does not imply that $k = 2$, since you can have (for example) a star graph.
  $endgroup$
  – Michael Biro
  Mar 21 at 21:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The degree can be much larger than 2 though. Consider for $n$ even and arbitrarily large the graph $K_n/2,n/2$. Every vertex has degree $n/2 >> 2$. It however does have no more than $n/2*(n-n/2)$ edges...
  $endgroup$
  – Mike
  Mar 21 at 22:04
  
  

  
  
  
  

add a comment | 

1

2

$begingroup$

Having a graph $G$ which is simple and non-directed with $n$ vertices and max degree of a vertex $k$. Then show if it does not contain $K_3$ as induced subgraph then that proves $|E(G)|le (n-k)k$

So,having to find an upper limit to the number of edges.
My thoughts so far are:

1)If it does not contain an induced subgraph of $K_3$ then it does not have any kind of bigger $K$ and then the degree of $k$ is $2$.

Extra thought(not complete):Having a vertex ν that is $k(=2)$ degree then compute the sum of degrees $V(G)-N(v)$. [$N(ν)$ is neighbourhood of $v$].I need some analysis if correct to this last statement.

combinatorics graph-theory

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

27k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Note that this does not imply that $k = 2$, since you can have (for example) a star graph.
  $endgroup$
  – Michael Biro
  Mar 21 at 21:29
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  The degree can be much larger than 2 though. Consider for $n$ even and arbitrarily large the graph $K_n/2,n/2$. Every vertex has degree $n/2 >> 2$. It however does have no more than $n/2*(n-n/2)$ edges...
  $endgroup$
  – Mike
  Mar 21 at 22:04
  
  

  
  
  
  

add a comment | 

$begingroup$

Having a graph $G$ which is simple and non-directed with $n$ vertices and max degree of a vertex $k$. Then show if it does not contain $K_3$ as induced subgraph then that proves $|E(G)|le (n-k)k$

So,having to find an upper limit to the number of edges.
My thoughts so far are:

1)If it does not contain an induced subgraph of $K_3$ then it does not have any kind of bigger $K$ and then the degree of $k$ is $2$.

Extra thought(not complete):Having a vertex ν that is $k(=2)$ degree then compute the sum of degrees $V(G)-N(v)$. [$N(ν)$ is neighbourhood of $v$].I need some analysis if correct to this last statement.

combinatorics graph-theory

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

27k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

$endgroup$

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

27k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

27k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

edited Mar 21 at 23:31

Mike Earnest

27k22152

edited Mar 21 at 23:31

Mike Earnest

27k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

asked Mar 21 at 19:08

AgaeusAgaeus

677

1 Answer
1

active

oldest

votes

3

$begingroup$

Let $v$ be a vertex of degree $k$. Then every vertex $u in N_G(v)$ cannot have a neighbor in $N_G(v)$ lest there be a triangle. So each such $u$ can have degree at most $N-k$; and there are $k$ such $u$. Every vertex $w not in N_G(v)$ [which includes $v$ itself] can have degree at most $k$ by the hypothesis that $G$ has maximum degree $k$; there are $N-k$ such $w$.

So
$$|E(G)| = frac12 times left(sum_u in N_G(v) d_G(u) + sum_w not in N_G(v) d_G(w) right)$$

$$le frac12 times left(k cdot (N-k) + (N-k)cdot kright)$$

which gives the desired bound.

share|cite|improve this answer

edited Mar 24 at 21:54

Mike Earnest

27k22152

answered Mar 21 at 21:54

MikeMike

4,611512

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I think your point (2) is not quite right. When $k=N-1$, then your linked answer implies a triangle free graph has at most $N^2/4$ edges, but this is not enough to show it has at most $k(N-k)=N-1$ edges.
  $endgroup$
  – Mike Earnest
  Mar 21 at 23:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are correct @MikeEarnest I just fixed
  $endgroup$
  – Mike
  Mar 22 at 0:18
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Sweet proof! :D
  $endgroup$
  – Mike Earnest
  Mar 22 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you @MikeEarnest!
  $endgroup$
  – Mike
  Mar 22 at 1:21
  

  
  
  
  

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%2f3157251%2ftriangle-free-graph-with-n-vertices-and-maximum-degree-k-has-at-most-kn-k%23new-answer', 'question_page');

);

Post as a guest

Name

Email

Required, but never shown

3

$begingroup$

Let $v$ be a vertex of degree $k$. Then every vertex $u in N_G(v)$ cannot have a neighbor in $N_G(v)$ lest there be a triangle. So each such $u$ can have degree at most $N-k$; and there are $k$ such $u$. Every vertex $w not in N_G(v)$ [which includes $v$ itself] can have degree at most $k$ by the hypothesis that $G$ has maximum degree $k$; there are $N-k$ such $w$.

So
$$|E(G)| = frac12 times left(sum_u in N_G(v) d_G(u) + sum_w not in N_G(v) d_G(w) right)$$

$$le frac12 times left(k cdot (N-k) + (N-k)cdot kright)$$

which gives the desired bound.

share|cite|improve this answer

edited Mar 24 at 21:54

Mike Earnest

27k22152

answered Mar 21 at 21:54

MikeMike

4,611512

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I think your point (2) is not quite right. When $k=N-1$, then your linked answer implies a triangle free graph has at most $N^2/4$ edges, but this is not enough to show it has at most $k(N-k)=N-1$ edges.
  $endgroup$
  – Mike Earnest
  Mar 21 at 23:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are correct @MikeEarnest I just fixed
  $endgroup$
  – Mike
  Mar 22 at 0:18
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Sweet proof! :D
  $endgroup$
  – Mike Earnest
  Mar 22 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you @MikeEarnest!
  $endgroup$
  – Mike
  Mar 22 at 1:21
  

  
  
  
  

add a comment | 

3

$begingroup$

Let $v$ be a vertex of degree $k$. Then every vertex $u in N_G(v)$ cannot have a neighbor in $N_G(v)$ lest there be a triangle. So each such $u$ can have degree at most $N-k$; and there are $k$ such $u$. Every vertex $w not in N_G(v)$ [which includes $v$ itself] can have degree at most $k$ by the hypothesis that $G$ has maximum degree $k$; there are $N-k$ such $w$.

So
$$|E(G)| = frac12 times left(sum_u in N_G(v) d_G(u) + sum_w not in N_G(v) d_G(w) right)$$

$$le frac12 times left(k cdot (N-k) + (N-k)cdot kright)$$

which gives the desired bound.

share|cite|improve this answer

edited Mar 24 at 21:54

Mike Earnest

27k22152

answered Mar 21 at 21:54

MikeMike

4,611512

$endgroup$

• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  I think your point (2) is not quite right. When $k=N-1$, then your linked answer implies a triangle free graph has at most $N^2/4$ edges, but this is not enough to show it has at most $k(N-k)=N-1$ edges.
  $endgroup$
  – Mike Earnest
  Mar 21 at 23:30
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  You are correct @MikeEarnest I just fixed
  $endgroup$
  – Mike
  Mar 22 at 0:18
  

  
  
  
  


• 
  
  
  

  
  1
  

  
  
  
  
  
  

  
  $begingroup$
  Sweet proof! :D
  $endgroup$
  – Mike Earnest
  Mar 22 at 0:27
  

  
  
  
  


• 
  
  
  

  
  

  
  
  
  
  
  

  
  $begingroup$
  Thank you @MikeEarnest!
  $endgroup$
  – Mike
  Mar 22 at 1:21
  

  
  
  
  

add a comment | 

$begingroup$

Let $v$ be a vertex of degree $k$. Then every vertex $u in N_G(v)$ cannot have a neighbor in $N_G(v)$ lest there be a triangle. So each such $u$ can have degree at most $N-k$; and there are $k$ such $u$. Every vertex $w not in N_G(v)$ [which includes $v$ itself] can have degree at most $k$ by the hypothesis that $G$ has maximum degree $k$; there are $N-k$ such $w$.

So
$$|E(G)| = frac12 times left(sum_u in N_G(v) d_G(u) + sum_w not in N_G(v) d_G(w) right)$$

$$le frac12 times left(k cdot (N-k) + (N-k)cdot kright)$$

which gives the desired bound.

share|cite|improve this answer

edited Mar 24 at 21:54

Mike Earnest

27k22152

answered Mar 21 at 21:54

MikeMike

4,611512

$endgroup$

share|cite|improve this answer

edited Mar 24 at 21:54

Mike Earnest

27k22152

answered Mar 21 at 21:54

MikeMike

4,611512

edited Mar 24 at 21:54

Mike Earnest

27k22152

edited Mar 24 at 21:54

Mike Earnest

27k22152

answered Mar 21 at 21:54

MikeMike

4,611512

answered Mar 21 at 21:54

MikeMike

4,611512