existence of a certain subset of vertices in a graph
Take an undirected graph $G=(V,E)$. For any subset $Msubseteq V$, we define ${rm deg}_M(v)=|{kin M:(v,k)in E}|$, namely, the number of neighbors of $v$ in $M$.
Is it true that, there exists a subset $Msubseteq V$ such that, for every $vin M$, ${rm deg}_M(v)leq 3$, and for every $v'in Vsetminus M$, ${rm deg}_M(v')geq 4$?
Note that, some obvious cases. If nobody are friends, we can simply take $V$ to be the entire set. Similarly, if $G$ is fully connected, then any $4-$element subset work. I tried to reason in the following way, take a maximal (in the sense of cardinality) $M$, such that, for every $vin M$, ${rm deg}_M(v)leq 3$. Now, for any point outside, if it has $geq 4$ neighbors, we are done. If not, then there are points in $M$, which are neighbors of $v$, such that, their in$-M$ degree is precisely $3$, but this did not lead me to anywhere.
co.combinatorics graph-theory
asked Nov 22 at 23:50
kawa
1587
add a comment |
Take an undirected graph $G=(V,E)$. For any subset $Msubseteq V$, we define ${rm deg}_M(v)=|{kin M:(v,k)in E}|$, namely, the number of neighbors of $v$ in $M$.
Is it true that, there exists a subset $Msubseteq V$ such that, for every $vin M$, ${rm deg}_M(v)leq 3$, and for every $v'in Vsetminus M$, ${rm deg}_M(v')geq 4$?
Note that, some obvious cases. If nobody are friends, we can simply take $V$ to be the entire set. Similarly, if $G$ is fully connected, then any $4-$element subset work. I tried to reason in the following way, take a maximal (in the sense of cardinality) $M$, such that, for every $vin M$, ${rm deg}_M(v)leq 3$. Now, for any point outside, if it has $geq 4$ neighbors, we are done. If not, then there are points in $M$, which are neighbors of $v$, such that, their in$-M$ degree is precisely $3$, but this did not lead me to anywhere.
co.combinatorics graph-theory
asked Nov 22 at 23:50
kawa
1587
add a comment |
Take an undirected graph $G=(V,E)$. For any subset $Msubseteq V$, we define ${rm deg}_M(v)=|{kin M:(v,k)in E}|$, namely, the number of neighbors of $v$ in $M$.
Is it true that, there exists a subset $Msubseteq V$ such that, for every $vin M$, ${rm deg}_M(v)leq 3$, and for every $v'in Vsetminus M$, ${rm deg}_M(v')geq 4$?
Note that, some obvious cases. If nobody are friends, we can simply take $V$ to be the entire set. Similarly, if $G$ is fully connected, then any $4-$element subset work. I tried to reason in the following way, take a maximal (in the sense of cardinality) $M$, such that, for every $vin M$, ${rm deg}_M(v)leq 3$. Now, for any point outside, if it has $geq 4$ neighbors, we are done. If not, then there are points in $M$, which are neighbors of $v$, such that, their in$-M$ degree is precisely $3$, but this did not lead me to anywhere.
co.combinatorics graph-theory
asked Nov 22 at 23:50
kawa
1587
Take an undirected graph $G=(V,E)$. For any subset $Msubseteq V$, we define ${rm deg}_M(v)=|{kin M:(v,k)in E}|$, namely, the number of neighbors of $v$ in $M$.
Is it true that, there exists a subset $Msubseteq V$ such that, for every $vin M$, ${rm deg}_M(v)leq 3$, and for every $v'in Vsetminus M$, ${rm deg}_M(v')geq 4$?
Note that, some obvious cases. If nobody are friends, we can simply take $V$ to be the entire set. Similarly, if $G$ is fully connected, then any $4-$element subset work. I tried to reason in the following way, take a maximal (in the sense of cardinality) $M$, such that, for every $vin M$, ${rm deg}_M(v)leq 3$. Now, for any point outside, if it has $geq 4$ neighbors, we are done. If not, then there are points in $M$, which are neighbors of $v$, such that, their in$-M$ degree is precisely $3$, but this did not lead me to anywhere.
co.combinatorics graph-theory
co.combinatorics graph-theory
asked Nov 22 at 23:50
kawa
1587
asked Nov 22 at 23:50
kawa
1587
asked Nov 22 at 23:50
kawa
1587
asked Nov 22 at 23:50
kawa
1587
asked Nov 22 at 23:50
kawa
1587
1587
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
Let us consider all sets $M$ with $d_M(v)le 3$ for all $vin M$ (I'll write $d$ instead of $rm{deg}$) and choose the set that maximizes
$$
|M|-frac 14 E(M)
$$
where $E(M)$ is the number of edges between the vertices in $M$.
Assume that there is a vertex $w$ with $d_M(w)le 3$. We can try to add it to $M$ but it may spoil some its neighbors in $M$ (those that had degree $3$ in $M$ already). Then we may just delete the bad neighbors one by one as long as their degree is $4$ (after the first deletion we can improve other vertices too, so we may delete only part of spoiled neighbors and the rest may get their low degree recovered). If we do $k$ deletions, we get $|M|to |M|+1-k$, $E(M)to le E(M)+3-4k$, which certainly increases the functional by at least $frac 14$. Thus the trivial algorithm (add a vertex and remove the resulting conflicts, if any, one by one) works and achieves the desired result in $4|V|$ steps at the worst.
answered Nov 23 at 3:31
fedja
37.4k7108202
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
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: "504"
};
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%2fmathoverflow.net%2fquestions%2f315994%2fexistence-of-a-certain-subset-of-vertices-in-a-graph%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
Let us consider all sets $M$ with $d_M(v)le 3$ for all $vin M$ (I'll write $d$ instead of $rm{deg}$) and choose the set that maximizes
$$
|M|-frac 14 E(M)
$$
where $E(M)$ is the number of edges between the vertices in $M$.
Assume that there is a vertex $w$ with $d_M(w)le 3$. We can try to add it to $M$ but it may spoil some its neighbors in $M$ (those that had degree $3$ in $M$ already). Then we may just delete the bad neighbors one by one as long as their degree is $4$ (after the first deletion we can improve other vertices too, so we may delete only part of spoiled neighbors and the rest may get their low degree recovered). If we do $k$ deletions, we get $|M|to |M|+1-k$, $E(M)to le E(M)+3-4k$, which certainly increases the functional by at least $frac 14$. Thus the trivial algorithm (add a vertex and remove the resulting conflicts, if any, one by one) works and achieves the desired result in $4|V|$ steps at the worst.
answered Nov 23 at 3:31
fedja
37.4k7108202
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
add a comment |
Let us consider all sets $M$ with $d_M(v)le 3$ for all $vin M$ (I'll write $d$ instead of $rm{deg}$) and choose the set that maximizes
$$
|M|-frac 14 E(M)
$$
where $E(M)$ is the number of edges between the vertices in $M$.
Assume that there is a vertex $w$ with $d_M(w)le 3$. We can try to add it to $M$ but it may spoil some its neighbors in $M$ (those that had degree $3$ in $M$ already). Then we may just delete the bad neighbors one by one as long as their degree is $4$ (after the first deletion we can improve other vertices too, so we may delete only part of spoiled neighbors and the rest may get their low degree recovered). If we do $k$ deletions, we get $|M|to |M|+1-k$, $E(M)to le E(M)+3-4k$, which certainly increases the functional by at least $frac 14$. Thus the trivial algorithm (add a vertex and remove the resulting conflicts, if any, one by one) works and achieves the desired result in $4|V|$ steps at the worst.
answered Nov 23 at 3:31
fedja
37.4k7108202
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
add a comment |
Let us consider all sets $M$ with $d_M(v)le 3$ for all $vin M$ (I'll write $d$ instead of $rm{deg}$) and choose the set that maximizes
$$
|M|-frac 14 E(M)
$$
where $E(M)$ is the number of edges between the vertices in $M$.
Assume that there is a vertex $w$ with $d_M(w)le 3$. We can try to add it to $M$ but it may spoil some its neighbors in $M$ (those that had degree $3$ in $M$ already). Then we may just delete the bad neighbors one by one as long as their degree is $4$ (after the first deletion we can improve other vertices too, so we may delete only part of spoiled neighbors and the rest may get their low degree recovered). If we do $k$ deletions, we get $|M|to |M|+1-k$, $E(M)to le E(M)+3-4k$, which certainly increases the functional by at least $frac 14$. Thus the trivial algorithm (add a vertex and remove the resulting conflicts, if any, one by one) works and achieves the desired result in $4|V|$ steps at the worst.
answered Nov 23 at 3:31
fedja
37.4k7108202
Let us consider all sets $M$ with $d_M(v)le 3$ for all $vin M$ (I'll write $d$ instead of $rm{deg}$) and choose the set that maximizes
$$
|M|-frac 14 E(M)
$$
where $E(M)$ is the number of edges between the vertices in $M$.
Assume that there is a vertex $w$ with $d_M(w)le 3$. We can try to add it to $M$ but it may spoil some its neighbors in $M$ (those that had degree $3$ in $M$ already). Then we may just delete the bad neighbors one by one as long as their degree is $4$ (after the first deletion we can improve other vertices too, so we may delete only part of spoiled neighbors and the rest may get their low degree recovered). If we do $k$ deletions, we get $|M|to |M|+1-k$, $E(M)to le E(M)+3-4k$, which certainly increases the functional by at least $frac 14$. Thus the trivial algorithm (add a vertex and remove the resulting conflicts, if any, one by one) works and achieves the desired result in $4|V|$ steps at the worst.
answered Nov 23 at 3:31
fedja
37.4k7108202
answered Nov 23 at 3:31
fedja
37.4k7108202
answered Nov 23 at 3:31
fedja
37.4k7108202
answered Nov 23 at 3:31
fedja
37.4k7108202
37.4k7108202
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
add a comment |
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
And of course the same argument shows that, for any nonnegative integer $d$ and any finite graph $G=(V,E)$, there is a set $Msubseteq V$ such that $M={xin V:|N(x)cap M|le d}$. Is this also true for infinite graphs?
– bof
Nov 23 at 5:49
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
@bof Hard to tell... Of course, when we have some sort of compactness principle, we can reduce the question to the finite case, but what would you do in the case of the unit distance graph for the points in $mathbb R^n$, for instance?
– fedja
Nov 23 at 22:19
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
At least it's true for locally finite graphs, by compactness. Right?
– bof
Nov 24 at 12:46
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
The unit distance graph on $mathbb R^n$ is easy. The cases $n=0$ (finite graph) and $n=1$ (locally finite) are trivial. For $nge2$ an easy transfinite construction (with the axiom of choice of course) gets us a set $Asubsetmathbb R^n$ such that $|N(x)cap A|=0$ for $xin A$ while $|N(x)cap A|=|mathbb R|$ for $xinmathbb R^nsetminus A$.
– bof
Nov 27 at 6:57
add a comment |
Thanks for contributing an answer to MathOverflow!
- 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.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- 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.
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%2fmathoverflow.net%2fquestions%2f315994%2fexistence-of-a-certain-subset-of-vertices-in-a-graph%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
