Prove there is a unique connected simple graph with degree sequence $2,2,dots,2,1,1$.
My attempt: Assume that graph is connected, that unique graph is basically a "line" with vertices on it. The vertices with degree $1$ and these vertices can only be on the two ends, and vertices with degree $2$ are in the middle. Am I correct? Is there a formal way to present it?
discrete-mathematics graph-theory
edited Nov 20 '18 at 22:51
bof
50.3k457119
asked Nov 19 '18 at 18:03
Thomas
1046
add a comment |
My attempt: Assume that graph is connected, that unique graph is basically a "line" with vertices on it. The vertices with degree $1$ and these vertices can only be on the two ends, and vertices with degree $2$ are in the middle. Am I correct? Is there a formal way to present it?
discrete-mathematics graph-theory
edited Nov 20 '18 at 22:51
bof
50.3k457119
asked Nov 19 '18 at 18:03
Thomas
1046
1
But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title?
– bof
Nov 20 '18 at 3:32
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
Nov 20 '18 at 15:58
add a comment |
My attempt: Assume that graph is connected, that unique graph is basically a "line" with vertices on it. The vertices with degree $1$ and these vertices can only be on the two ends, and vertices with degree $2$ are in the middle. Am I correct? Is there a formal way to present it?
discrete-mathematics graph-theory
edited Nov 20 '18 at 22:51
bof
50.3k457119
asked Nov 19 '18 at 18:03
Thomas
1046
My attempt: Assume that graph is connected, that unique graph is basically a "line" with vertices on it. The vertices with degree $1$ and these vertices can only be on the two ends, and vertices with degree $2$ are in the middle. Am I correct? Is there a formal way to present it?
discrete-mathematics graph-theory
discrete-mathematics graph-theory
edited Nov 20 '18 at 22:51
bof
50.3k457119
asked Nov 19 '18 at 18:03
Thomas
1046
edited Nov 20 '18 at 22:51
bof
50.3k457119
asked Nov 19 '18 at 18:03
Thomas
1046
edited Nov 20 '18 at 22:51
bof
50.3k457119
edited Nov 20 '18 at 22:51
bof
50.3k457119
edited Nov 20 '18 at 22:51
bof
50.3k457119
50.3k457119
asked Nov 19 '18 at 18:03
Thomas
1046
asked Nov 19 '18 at 18:03
Thomas
1046
asked Nov 19 '18 at 18:03
Thomas
1046
1046
1
But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title?
– bof
Nov 20 '18 at 3:32
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
Nov 20 '18 at 15:58
add a comment |
1
But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title?
– bof
Nov 20 '18 at 3:32
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
Nov 20 '18 at 15:58
1
1
But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title?
– bof
Nov 20 '18 at 3:32
But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title?
– bof
Nov 20 '18 at 3:32
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
Nov 20 '18 at 15:58
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
Nov 20 '18 at 15:58
add a comment |
1 Answer
1
active
oldest
votes
The formal notion of "equality" between graphs is isomorphism. Technically, you can have different graphs with that degree sequence: the first graph can have vertex set ${1, 2, 3, dots n}$, while the the other can have vertex set ${A, B, C, dots, Z}$. What's important is, we can prove that they are isomorphic.
Assume there are two graphs, $G(V, E)$ and $G^prime(V^prime, E^prime)$, both with degree sequence $2, 2, dots, 2, 1, 1$. We will construct a function $f: V to V^prime$ such, that $(v_1, v_2) in V iff (f(v_1), f(v_2)) in V^prime$. The existence of such function proves the isomorphism.
Let $n = |V| = |V^prime|$, and let $v_1$ and $v_n$ be the 1-degree vertices of $G$. There exists a path $v_1, v_2, v_3, dots, v_n$ between $v_1$ and $v_n$ (G is connected). Assume vertex $u$ is not in the path. $v_1$ and $v_n$ have degree 1, and each have a neighbor in the path. $v_i$ for $i neq 1, n$ has degree 2 and has 2 neighbors in the path. Therefore, there is no edge connecting vertices in the path with a vertex outside the path, which breaks the connectivity condition. So all vertices are in the path, and its length is $n$.
Similarly, we can construct a path of length $n$, $v_1^prime, v_2^prime, dots v_n^prime$ of length $n$ between the 1-degree vertices in $G^prime$, and it will ocntain all vertices in $V^prime$.
Let $f(v_i) = v_i^prime$. The neighbors of $v_i$ and $v_{i-1}$ and $v_{i+1}$ (or only one if $i in {1, n}$, and the neighbors of $f_{v_i} = v_i^prime$ are exactly $v_{i-1}^prime = f(v_{i-1})$ and $v_{i+1}^prime = f(v_{i+1})$, as desired.
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
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%2f3005275%2fprove-there-is-a-unique-connected-simple-graph-with-degree-sequence-2-2-dots-2%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
The formal notion of "equality" between graphs is isomorphism. Technically, you can have different graphs with that degree sequence: the first graph can have vertex set ${1, 2, 3, dots n}$, while the the other can have vertex set ${A, B, C, dots, Z}$. What's important is, we can prove that they are isomorphic.
Assume there are two graphs, $G(V, E)$ and $G^prime(V^prime, E^prime)$, both with degree sequence $2, 2, dots, 2, 1, 1$. We will construct a function $f: V to V^prime$ such, that $(v_1, v_2) in V iff (f(v_1), f(v_2)) in V^prime$. The existence of such function proves the isomorphism.
Let $n = |V| = |V^prime|$, and let $v_1$ and $v_n$ be the 1-degree vertices of $G$. There exists a path $v_1, v_2, v_3, dots, v_n$ between $v_1$ and $v_n$ (G is connected). Assume vertex $u$ is not in the path. $v_1$ and $v_n$ have degree 1, and each have a neighbor in the path. $v_i$ for $i neq 1, n$ has degree 2 and has 2 neighbors in the path. Therefore, there is no edge connecting vertices in the path with a vertex outside the path, which breaks the connectivity condition. So all vertices are in the path, and its length is $n$.
Similarly, we can construct a path of length $n$, $v_1^prime, v_2^prime, dots v_n^prime$ of length $n$ between the 1-degree vertices in $G^prime$, and it will ocntain all vertices in $V^prime$.
Let $f(v_i) = v_i^prime$. The neighbors of $v_i$ and $v_{i-1}$ and $v_{i+1}$ (or only one if $i in {1, n}$, and the neighbors of $f_{v_i} = v_i^prime$ are exactly $v_{i-1}^prime = f(v_{i-1})$ and $v_{i+1}^prime = f(v_{i+1})$, as desired.
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
add a comment |
The formal notion of "equality" between graphs is isomorphism. Technically, you can have different graphs with that degree sequence: the first graph can have vertex set ${1, 2, 3, dots n}$, while the the other can have vertex set ${A, B, C, dots, Z}$. What's important is, we can prove that they are isomorphic.
Assume there are two graphs, $G(V, E)$ and $G^prime(V^prime, E^prime)$, both with degree sequence $2, 2, dots, 2, 1, 1$. We will construct a function $f: V to V^prime$ such, that $(v_1, v_2) in V iff (f(v_1), f(v_2)) in V^prime$. The existence of such function proves the isomorphism.
Let $n = |V| = |V^prime|$, and let $v_1$ and $v_n$ be the 1-degree vertices of $G$. There exists a path $v_1, v_2, v_3, dots, v_n$ between $v_1$ and $v_n$ (G is connected). Assume vertex $u$ is not in the path. $v_1$ and $v_n$ have degree 1, and each have a neighbor in the path. $v_i$ for $i neq 1, n$ has degree 2 and has 2 neighbors in the path. Therefore, there is no edge connecting vertices in the path with a vertex outside the path, which breaks the connectivity condition. So all vertices are in the path, and its length is $n$.
Similarly, we can construct a path of length $n$, $v_1^prime, v_2^prime, dots v_n^prime$ of length $n$ between the 1-degree vertices in $G^prime$, and it will ocntain all vertices in $V^prime$.
Let $f(v_i) = v_i^prime$. The neighbors of $v_i$ and $v_{i-1}$ and $v_{i+1}$ (or only one if $i in {1, n}$, and the neighbors of $f_{v_i} = v_i^prime$ are exactly $v_{i-1}^prime = f(v_{i-1})$ and $v_{i+1}^prime = f(v_{i+1})$, as desired.
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
add a comment |
The formal notion of "equality" between graphs is isomorphism. Technically, you can have different graphs with that degree sequence: the first graph can have vertex set ${1, 2, 3, dots n}$, while the the other can have vertex set ${A, B, C, dots, Z}$. What's important is, we can prove that they are isomorphic.
Assume there are two graphs, $G(V, E)$ and $G^prime(V^prime, E^prime)$, both with degree sequence $2, 2, dots, 2, 1, 1$. We will construct a function $f: V to V^prime$ such, that $(v_1, v_2) in V iff (f(v_1), f(v_2)) in V^prime$. The existence of such function proves the isomorphism.
Let $n = |V| = |V^prime|$, and let $v_1$ and $v_n$ be the 1-degree vertices of $G$. There exists a path $v_1, v_2, v_3, dots, v_n$ between $v_1$ and $v_n$ (G is connected). Assume vertex $u$ is not in the path. $v_1$ and $v_n$ have degree 1, and each have a neighbor in the path. $v_i$ for $i neq 1, n$ has degree 2 and has 2 neighbors in the path. Therefore, there is no edge connecting vertices in the path with a vertex outside the path, which breaks the connectivity condition. So all vertices are in the path, and its length is $n$.
Similarly, we can construct a path of length $n$, $v_1^prime, v_2^prime, dots v_n^prime$ of length $n$ between the 1-degree vertices in $G^prime$, and it will ocntain all vertices in $V^prime$.
Let $f(v_i) = v_i^prime$. The neighbors of $v_i$ and $v_{i-1}$ and $v_{i+1}$ (or only one if $i in {1, n}$, and the neighbors of $f_{v_i} = v_i^prime$ are exactly $v_{i-1}^prime = f(v_{i-1})$ and $v_{i+1}^prime = f(v_{i+1})$, as desired.
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
The formal notion of "equality" between graphs is isomorphism. Technically, you can have different graphs with that degree sequence: the first graph can have vertex set ${1, 2, 3, dots n}$, while the the other can have vertex set ${A, B, C, dots, Z}$. What's important is, we can prove that they are isomorphic.
Assume there are two graphs, $G(V, E)$ and $G^prime(V^prime, E^prime)$, both with degree sequence $2, 2, dots, 2, 1, 1$. We will construct a function $f: V to V^prime$ such, that $(v_1, v_2) in V iff (f(v_1), f(v_2)) in V^prime$. The existence of such function proves the isomorphism.
Let $n = |V| = |V^prime|$, and let $v_1$ and $v_n$ be the 1-degree vertices of $G$. There exists a path $v_1, v_2, v_3, dots, v_n$ between $v_1$ and $v_n$ (G is connected). Assume vertex $u$ is not in the path. $v_1$ and $v_n$ have degree 1, and each have a neighbor in the path. $v_i$ for $i neq 1, n$ has degree 2 and has 2 neighbors in the path. Therefore, there is no edge connecting vertices in the path with a vertex outside the path, which breaks the connectivity condition. So all vertices are in the path, and its length is $n$.
Similarly, we can construct a path of length $n$, $v_1^prime, v_2^prime, dots v_n^prime$ of length $n$ between the 1-degree vertices in $G^prime$, and it will ocntain all vertices in $V^prime$.
Let $f(v_i) = v_i^prime$. The neighbors of $v_i$ and $v_{i-1}$ and $v_{i+1}$ (or only one if $i in {1, n}$, and the neighbors of $f_{v_i} = v_i^prime$ are exactly $v_{i-1}^prime = f(v_{i-1})$ and $v_{i+1}^prime = f(v_{i+1})$, as desired.
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
answered Nov 19 '18 at 19:44
Todor Markov
1,11317
1,11317
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.
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%2fmath.stackexchange.com%2fquestions%2f3005275%2fprove-there-is-a-unique-connected-simple-graph-with-degree-sequence-2-2-dots-2%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
But the statement in the title of your question is false, because the graph is not unique without assuming connectedness. Or was the original question about connected graphs, and you accidentally omitted the word "connected" from the title?
– bof
Nov 20 '18 at 3:32
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
Nov 20 '18 at 15:58