Fdtxjr

Could an aircraft fly or hover using only jets of compressed air?

dbcc cleantable batch size explanation

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

Does an object always see its latest internal state irrespective of thread?

Today is the Center

Book with a girl whose grandma is a phoenix, cover depicts the emerald/green-eyed blonde girl

"You are your self first supporter", a more proper way to say it

tikz convert color string to hex value

Is it legal for company to use my work email to pretend I still work there?

Why doesn't H₄O²⁺ exist?

Roll the carpet

Is it unprofessional to ask if a job posting on GlassDoor is real?

Is it inappropriate for a student to attend their mentor's dissertation defense?

Can a Cauchy sequence converge for one metric while not converging for another?

Why is consensus so controversial in Britain?

Are astronomers waiting to see something in an image from a gravitational lens that they've already seen in an adjacent image?

What defenses are there against being summoned by the Gate spell?

Convert two switches to a dual stack, and add outlet - possible here?

Alternative to sending password over mail?

Replacing matching entries in one column of a file by another column from a different file

What is the word for reserving something for yourself before others do?

What does the "remote control" for a QF-4 look like?

Codimension of non-flat locus

What is a clear way to write a bar that has an extra beat?

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

26.9k22152

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

26.9k22152

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

26.9k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

$endgroup$

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

26.9k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

share|cite|improve this question

edited Mar 21 at 23:31

Mike Earnest

26.9k22152

asked Mar 21 at 19:08

AgaeusAgaeus

677

edited Mar 21 at 23:31

Mike Earnest

26.9k22152

edited Mar 21 at 23:31

Mike Earnest

26.9k22152

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

26.9k22152

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

26.9k22152

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

26.9k22152

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

26.9k22152

answered Mar 21 at 21:54

MikeMike

4,611512

$endgroup$

share|cite|improve this answer

edited Mar 24 at 21:54

Mike Earnest

26.9k22152

answered Mar 21 at 21:54

MikeMike

4,611512

edited Mar 24 at 21:54

Mike Earnest

26.9k22152

edited Mar 24 at 21:54

Mike Earnest

26.9k22152

answered Mar 21 at 21:54

MikeMike

4,611512

answered Mar 21 at 21:54

MikeMike

4,611512