Mixing
Prove there is a unique connected simple graph with degree sequence $2,2,dots,2,1,1$.
up vote
3
down vote
favorite
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 19 hours ago
bof
48.5k450115
asked yesterday
Thomas
896
add a comment |
up vote
3
down vote
favorite
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 19 hours ago
bof
48.5k450115
asked yesterday
Thomas
896
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
yesterday
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
yesterday
add a comment |
up vote
3
down vote
favorite
up vote
3
down vote
favorite
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 19 hours ago
bof
48.5k450115
asked yesterday
Thomas
896
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 19 hours ago
bof
48.5k450115
asked yesterday
Thomas
896
edited 19 hours ago
bof
48.5k450115
asked yesterday
Thomas
896
edited 19 hours ago
bof
48.5k450115
edited 19 hours ago
bof
48.5k450115
edited 19 hours ago
bof
48.5k450115
48.5k450115
asked yesterday
Thomas
896
asked yesterday
Thomas
896
asked yesterday
Thomas
896
896
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
yesterday
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
yesterday
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
yesterday
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
yesterday
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
yesterday
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
yesterday
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
yesterday
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
yesterday
add a comment |
1 Answer
1
active
oldest
votes
up vote
1
down vote
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 yesterday
Todor Markov
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
1
down vote
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 yesterday
Todor Markov
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
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 yesterday
Todor Markov
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
1
down vote
up vote
1
down vote
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 yesterday
Todor Markov
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
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 yesterday
Todor Markov
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
Todor Markov
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
answered yesterday
Todor Markov
3365
answered yesterday
Todor Markov
3365
3365
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Todor Markov is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
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
yesterday
@bof Yes it's assumed to be connected. I should've been more clear
– Thomas
yesterday