Triangle free graph with $n$ vertices and maximum degree $k$ has at most $k(n-k)$ edges. The...
Is it ethical to upload a automatically generated paper to a non peer-reviewed site as part of a larger research?
APIPA and LAN Broadcast Domain
How to type a long/em dash `—`
Why doesn't UInt have a toDouble()?
Match Roman Numerals
What to do when moving next to a bird sanctuary with a loosely-domesticated cat?
Keeping a retro style to sci-fi spaceships?
Getting crown tickets for Statue of Liberty
What does もの mean in this sentence?
What could be the right powersource for 15 seconds lifespan disposable giant chainsaw?
What is the meaning of Triage in Cybersec world?
Is it okay to consider publishing in my first year of PhD?
Can an undergraduate be advised by a professor who is very far away?
Is it possible for absolutely everyone to attain enlightenment?
The phrase "to the numbers born"?
Can withdrawing asylum be illegal?
What do I do when my TA workload is more than expected?
Is it a good practice to use a static variable in a Test Class and use that in the actual class instead of Test.isRunningTest()?
Geography at the pixel level
Can there be female White Walkers?
Straighten subgroup lattice
For what reasons would an animal species NOT cross a *horizontal* land bridge?
Worn-tile Scrabble
Why couldn't they take pictures of a closer black hole?
Triangle free graph with $n$ vertices and maximum degree $k$ has at most $k(n-k)$ edges.
The 2019 Stack Overflow Developer Survey Results Are InGraph 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
$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
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
asked Mar 21 at 19:08
AgaeusAgaeus
727
$endgroup$
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
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
asked Mar 21 at 19:08
AgaeusAgaeus
727
$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
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
asked Mar 21 at 19:08
AgaeusAgaeus
727
$endgroup$
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
combinatorics graph-theory
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
asked Mar 21 at 19:08
AgaeusAgaeus
727
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
asked Mar 21 at 19:08
AgaeusAgaeus
727
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
edited Mar 21 at 23:31
Mike Earnest
27.6k22152
27.6k22152
asked Mar 21 at 19:08
AgaeusAgaeus
727
asked Mar 21 at 19:08
AgaeusAgaeus
727
asked Mar 21 at 19:08
AgaeusAgaeus
727
727
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
$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
1
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$
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
$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 Answer
1
active
oldest
votes
$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)| = frac{1}{2} times left(sum_{u in N_G(v)} d_G(u) + sum_{w not in N_G(v)} d_G(w) right)$$
$$le frac{1}{2} times left(k cdot (N-k) + (N-k)cdot kright)$$
which gives the desired bound.
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
answered Mar 21 at 21:54
MikeMike
4,621512
$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
});
}
});
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%2f3157251%2ftriangle-free-graph-with-n-vertices-and-maximum-degree-k-has-at-most-kn-k%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$
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)| = frac{1}{2} times left(sum_{u in N_G(v)} d_G(u) + sum_{w not in N_G(v)} d_G(w) right)$$
$$le frac{1}{2} times left(k cdot (N-k) + (N-k)cdot kright)$$
which gives the desired bound.
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
answered Mar 21 at 21:54
MikeMike
4,621512
$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)| = frac{1}{2} times left(sum_{u in N_G(v)} d_G(u) + sum_{w not in N_G(v)} d_G(w) right)$$
$$le frac{1}{2} times left(k cdot (N-k) + (N-k)cdot kright)$$
which gives the desired bound.
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
answered Mar 21 at 21:54
MikeMike
4,621512
$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)| = frac{1}{2} times left(sum_{u in N_G(v)} d_G(u) + sum_{w not in N_G(v)} d_G(w) right)$$
$$le frac{1}{2} times left(k cdot (N-k) + (N-k)cdot kright)$$
which gives the desired bound.
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
answered Mar 21 at 21:54
MikeMike
4,621512
$endgroup$
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)| = frac{1}{2} times left(sum_{u in N_G(v)} d_G(u) + sum_{w not in N_G(v)} d_G(w) right)$$
$$le frac{1}{2} times left(k cdot (N-k) + (N-k)cdot kright)$$
which gives the desired bound.
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
answered Mar 21 at 21:54
MikeMike
4,621512
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
edited Mar 24 at 21:54
Mike Earnest
27.6k22152
27.6k22152
answered Mar 21 at 21:54
MikeMike
4,621512
answered Mar 21 at 21:54
MikeMike
4,621512
answered Mar 21 at 21:54
MikeMike
4,621512
4,621512
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 |
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
1
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$
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
$begingroup$
You are correct @MikeEarnest I just fixed
$endgroup$
– Mike
Mar 22 at 0:18
1
1
$begingroup$
Sweet proof! :D
$endgroup$
– Mike Earnest
Mar 22 at 0:27
$begingroup$
Sweet proof! :D
$endgroup$
– Mike Earnest
Mar 22 at 0:27
$begingroup$
Thank you @MikeEarnest!
$endgroup$
– Mike
Mar 22 at 1:21
$begingroup$
Thank you @MikeEarnest!
$endgroup$
– Mike
Mar 22 at 1:21
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%2f3157251%2ftriangle-free-graph-with-n-vertices-and-maximum-degree-k-has-at-most-kn-k%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
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