Prove that $(n, n, n-1, n-1, ldots , 4, 4, 3, 3, 2, 2, 1, 1)$ is a graphic!
$begingroup$
A sequence of non-negative integers is called graphic if there exist a graph whose degree sequence is precisely that sequence.
For example, $(1, 1, 1, 1, 1, 1)$ is a graphic since it's the degree sequence of graph
and $(3, 1, 0, 0, 0)$ is not a graphic since there is no graph with one vertex of degree 3, one vertex of degree 1, and three vertices of degree 0.
Now, the question is prove that
$$(n, n, n-1, n-1, ldots, 4, 4, 3, 3, 2, 2, 1, 1)$$
is always a graphic.
My attempt is by construct the simple graph and find some pattern for building a larger one. Starting with $n=1$, then I try to construct $n=2$. Now, based on the result $n=2$, then again I construct for $n=3$, and so on.
But, after doing that process, I don't get at all the pattern for building such larger graph from previous graph. Everything seems randomly yet beautifully constructed. Here is my drawing process:
Please help me to prove this. Thanks before.
graph-theory
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
$endgroup$
add a comment |
$begingroup$
A sequence of non-negative integers is called graphic if there exist a graph whose degree sequence is precisely that sequence.
For example, $(1, 1, 1, 1, 1, 1)$ is a graphic since it's the degree sequence of graph
and $(3, 1, 0, 0, 0)$ is not a graphic since there is no graph with one vertex of degree 3, one vertex of degree 1, and three vertices of degree 0.
Now, the question is prove that
$$(n, n, n-1, n-1, ldots, 4, 4, 3, 3, 2, 2, 1, 1)$$
is always a graphic.
My attempt is by construct the simple graph and find some pattern for building a larger one. Starting with $n=1$, then I try to construct $n=2$. Now, based on the result $n=2$, then again I construct for $n=3$, and so on.
But, after doing that process, I don't get at all the pattern for building such larger graph from previous graph. Everything seems randomly yet beautifully constructed. Here is my drawing process:
Please help me to prove this. Thanks before.
graph-theory
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
$endgroup$
add a comment |
$begingroup$
A sequence of non-negative integers is called graphic if there exist a graph whose degree sequence is precisely that sequence.
For example, $(1, 1, 1, 1, 1, 1)$ is a graphic since it's the degree sequence of graph
and $(3, 1, 0, 0, 0)$ is not a graphic since there is no graph with one vertex of degree 3, one vertex of degree 1, and three vertices of degree 0.
Now, the question is prove that
$$(n, n, n-1, n-1, ldots, 4, 4, 3, 3, 2, 2, 1, 1)$$
is always a graphic.
My attempt is by construct the simple graph and find some pattern for building a larger one. Starting with $n=1$, then I try to construct $n=2$. Now, based on the result $n=2$, then again I construct for $n=3$, and so on.
But, after doing that process, I don't get at all the pattern for building such larger graph from previous graph. Everything seems randomly yet beautifully constructed. Here is my drawing process:
Please help me to prove this. Thanks before.
graph-theory
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
$endgroup$
A sequence of non-negative integers is called graphic if there exist a graph whose degree sequence is precisely that sequence.
For example, $(1, 1, 1, 1, 1, 1)$ is a graphic since it's the degree sequence of graph
and $(3, 1, 0, 0, 0)$ is not a graphic since there is no graph with one vertex of degree 3, one vertex of degree 1, and three vertices of degree 0.
Now, the question is prove that
$$(n, n, n-1, n-1, ldots, 4, 4, 3, 3, 2, 2, 1, 1)$$
is always a graphic.
My attempt is by construct the simple graph and find some pattern for building a larger one. Starting with $n=1$, then I try to construct $n=2$. Now, based on the result $n=2$, then again I construct for $n=3$, and so on.
But, after doing that process, I don't get at all the pattern for building such larger graph from previous graph. Everything seems randomly yet beautifully constructed. Here is my drawing process:
Please help me to prove this. Thanks before.
graph-theory
graph-theory
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
edited Feb 5 '12 at 13:32
Mas Adit
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
asked Feb 5 '12 at 13:27
Mas AditMas Adit
1238
1238
add a comment |
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
Suppose you started with a (n,n,n-1,n-1,...,1,1) graphic, and you want to add two nodes, A and B, to it. Connect A with one of each type of node that's already there: one n-node, one n-1 node, etc all the way to one 1-node. Also connect A to B, but connect B to nothing else.
Now lets think about what just happened.
- A has n+1 edges (n from connections to the original graph, plus one from it's connection to B).
- B has 1 edge
- half of the nodes (one of each type) in the original graph got their edgecount bumped up by 1, by getting connected to A.
So now there are two 2-nodes, two 3-nodes, ..., two n-nodes from the original graph, plus B and the 1-node that was unchanged as two 1-nodes, plus A and the n-node that got bumped up as two n+1-nodes. Thus a graphic one size bigger!
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
$endgroup$
add a comment |
$begingroup$
Yes there is an inductive procedure: Suppose $(n-1, n-1, n-2, n-2, ldots, 2, 2, 1, 1)$ is graphic, and let the graph have vertices labeled $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, ldots, v_2, w_2, v_1, w_1$, where subscripts equal degree of vertex. append two new verteces $v_0, w_0$. Now there is an easy way to add edges so that the degree list changes from $(n-1, n-1, ldots, 1, 1, 0, 0)$ to $(n, n, ldots, 2, 2, 1, 1)$. Each new edge must increase exactly two of the the degrees. Note, it's not necessary to show exactly what the new graph is, just that it exists. This may be where your induction got bogged down(?)
Hope this help!
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
$endgroup$
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%2f105970%2fprove-that-n-n-n-1-n-1-ldots-4-4-3-3-2-2-1-1-is-a-graphic%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
Suppose you started with a (n,n,n-1,n-1,...,1,1) graphic, and you want to add two nodes, A and B, to it. Connect A with one of each type of node that's already there: one n-node, one n-1 node, etc all the way to one 1-node. Also connect A to B, but connect B to nothing else.
Now lets think about what just happened.
- A has n+1 edges (n from connections to the original graph, plus one from it's connection to B).
- B has 1 edge
- half of the nodes (one of each type) in the original graph got their edgecount bumped up by 1, by getting connected to A.
So now there are two 2-nodes, two 3-nodes, ..., two n-nodes from the original graph, plus B and the 1-node that was unchanged as two 1-nodes, plus A and the n-node that got bumped up as two n+1-nodes. Thus a graphic one size bigger!
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
$endgroup$
add a comment |
$begingroup$
Suppose you started with a (n,n,n-1,n-1,...,1,1) graphic, and you want to add two nodes, A and B, to it. Connect A with one of each type of node that's already there: one n-node, one n-1 node, etc all the way to one 1-node. Also connect A to B, but connect B to nothing else.
Now lets think about what just happened.
- A has n+1 edges (n from connections to the original graph, plus one from it's connection to B).
- B has 1 edge
- half of the nodes (one of each type) in the original graph got their edgecount bumped up by 1, by getting connected to A.
So now there are two 2-nodes, two 3-nodes, ..., two n-nodes from the original graph, plus B and the 1-node that was unchanged as two 1-nodes, plus A and the n-node that got bumped up as two n+1-nodes. Thus a graphic one size bigger!
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
$endgroup$
add a comment |
$begingroup$
Suppose you started with a (n,n,n-1,n-1,...,1,1) graphic, and you want to add two nodes, A and B, to it. Connect A with one of each type of node that's already there: one n-node, one n-1 node, etc all the way to one 1-node. Also connect A to B, but connect B to nothing else.
Now lets think about what just happened.
- A has n+1 edges (n from connections to the original graph, plus one from it's connection to B).
- B has 1 edge
- half of the nodes (one of each type) in the original graph got their edgecount bumped up by 1, by getting connected to A.
So now there are two 2-nodes, two 3-nodes, ..., two n-nodes from the original graph, plus B and the 1-node that was unchanged as two 1-nodes, plus A and the n-node that got bumped up as two n+1-nodes. Thus a graphic one size bigger!
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
$endgroup$
Suppose you started with a (n,n,n-1,n-1,...,1,1) graphic, and you want to add two nodes, A and B, to it. Connect A with one of each type of node that's already there: one n-node, one n-1 node, etc all the way to one 1-node. Also connect A to B, but connect B to nothing else.
Now lets think about what just happened.
- A has n+1 edges (n from connections to the original graph, plus one from it's connection to B).
- B has 1 edge
- half of the nodes (one of each type) in the original graph got their edgecount bumped up by 1, by getting connected to A.
So now there are two 2-nodes, two 3-nodes, ..., two n-nodes from the original graph, plus B and the 1-node that was unchanged as two 1-nodes, plus A and the n-node that got bumped up as two n+1-nodes. Thus a graphic one size bigger!
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
answered Feb 5 '12 at 13:47
Nick AlgerNick Alger
9,83863267
9,83863267
add a comment |
add a comment |
$begingroup$
Yes there is an inductive procedure: Suppose $(n-1, n-1, n-2, n-2, ldots, 2, 2, 1, 1)$ is graphic, and let the graph have vertices labeled $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, ldots, v_2, w_2, v_1, w_1$, where subscripts equal degree of vertex. append two new verteces $v_0, w_0$. Now there is an easy way to add edges so that the degree list changes from $(n-1, n-1, ldots, 1, 1, 0, 0)$ to $(n, n, ldots, 2, 2, 1, 1)$. Each new edge must increase exactly two of the the degrees. Note, it's not necessary to show exactly what the new graph is, just that it exists. This may be where your induction got bogged down(?)
Hope this help!
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
$endgroup$
add a comment |
$begingroup$
Yes there is an inductive procedure: Suppose $(n-1, n-1, n-2, n-2, ldots, 2, 2, 1, 1)$ is graphic, and let the graph have vertices labeled $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, ldots, v_2, w_2, v_1, w_1$, where subscripts equal degree of vertex. append two new verteces $v_0, w_0$. Now there is an easy way to add edges so that the degree list changes from $(n-1, n-1, ldots, 1, 1, 0, 0)$ to $(n, n, ldots, 2, 2, 1, 1)$. Each new edge must increase exactly two of the the degrees. Note, it's not necessary to show exactly what the new graph is, just that it exists. This may be where your induction got bogged down(?)
Hope this help!
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
$endgroup$
add a comment |
$begingroup$
Yes there is an inductive procedure: Suppose $(n-1, n-1, n-2, n-2, ldots, 2, 2, 1, 1)$ is graphic, and let the graph have vertices labeled $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, ldots, v_2, w_2, v_1, w_1$, where subscripts equal degree of vertex. append two new verteces $v_0, w_0$. Now there is an easy way to add edges so that the degree list changes from $(n-1, n-1, ldots, 1, 1, 0, 0)$ to $(n, n, ldots, 2, 2, 1, 1)$. Each new edge must increase exactly two of the the degrees. Note, it's not necessary to show exactly what the new graph is, just that it exists. This may be where your induction got bogged down(?)
Hope this help!
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
$endgroup$
Yes there is an inductive procedure: Suppose $(n-1, n-1, n-2, n-2, ldots, 2, 2, 1, 1)$ is graphic, and let the graph have vertices labeled $v_{n-1}, w_{n-1}, v_{n-2}, w_{n-2}, ldots, v_2, w_2, v_1, w_1$, where subscripts equal degree of vertex. append two new verteces $v_0, w_0$. Now there is an easy way to add edges so that the degree list changes from $(n-1, n-1, ldots, 1, 1, 0, 0)$ to $(n, n, ldots, 2, 2, 1, 1)$. Each new edge must increase exactly two of the the degrees. Note, it's not necessary to show exactly what the new graph is, just that it exists. This may be where your induction got bogged down(?)
Hope this help!
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
answered Feb 5 '12 at 13:50
Shaun AultShaun Ault
7,8821828
7,8821828
add a comment |
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%2f105970%2fprove-that-n-n-n-1-n-1-ldots-4-4-3-3-2-2-1-1-is-a-graphic%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
