Mixing
![How many different $7$-digit numbers can be formed from $0,1,2,2,3,3,3$ assuming no number can start with $0$? How many numbers will end with $0$? [on hold]](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhZCTB4-bb-s-32SAm6ytjzFOU06cH9o8q-a_wq_UnH6lcd8hvws23CmBWHM6g256LzTX9yK1EiCCzTC1NSgtxlNk_J9hdr9bA3tD0Nqntbl521j4bLAm_uXPANuWLBhcCKTKzns2gaUodx/s72-c/1.jpg)
Closed Graph from a Collection of Vertices
Clash Royale CLAN TAG#URR8PPP
up vote
1
down vote
favorite
Say I have two types of vertices:
- (D) vertices have two edges
- (T) vertices have three edges
Given a collection of these vertices, is there any way to prove whether they can be joined edge-to-edge to form a closed (i.e. no free edges) graph in 3-space?
For example, say I have 3 (T) vertices and 1 (D) vertex. (Unless I've missed something obvious) there is no way to join these vertices into a closed graph in space, but I'm not able to come up with a proof. On the other hand, 4 (T) vertices and 0 (D) vertices form a simple tetrahedron.
What about higher-order examples, such as 12 (T) vertices and 4 (D) vertices? Ideally I would like to be able to construct an example of a graph in cases where they exist, at least for small collections like these, but this isn't tagged for constructive-mathematics because I don't consider construction an absolute requirement.
graph-theory 3d
asked Aug 1 at 20:40
realityChemist
1585
add a comment |Â
up vote
1
down vote
favorite
Say I have two types of vertices:
- (D) vertices have two edges
- (T) vertices have three edges
Given a collection of these vertices, is there any way to prove whether they can be joined edge-to-edge to form a closed (i.e. no free edges) graph in 3-space?
For example, say I have 3 (T) vertices and 1 (D) vertex. (Unless I've missed something obvious) there is no way to join these vertices into a closed graph in space, but I'm not able to come up with a proof. On the other hand, 4 (T) vertices and 0 (D) vertices form a simple tetrahedron.
What about higher-order examples, such as 12 (T) vertices and 4 (D) vertices? Ideally I would like to be able to construct an example of a graph in cases where they exist, at least for small collections like these, but this isn't tagged for constructive-mathematics because I don't consider construction an absolute requirement.
graph-theory 3d
asked Aug 1 at 20:40
realityChemist
1585
Where does 3-space come in? And what exactly is a free edge? Are you wondering if it is possible to construct a graph with a given number of D and T vertices?
– Morgan Rodgers
Aug 2 at 6:47
3-space comes in because these graphs represent something in the real world, although I guess the question is mathematically equivalent to the 2-D case as long as you allow edges to cross. And by "free edge" I mean an edge that's only connected to a vertex at one end. I think that because of the way graphs and edges are defined your rephrasing is equivalent and would be a more standard way to think about the question. The real-world analog is what lead me to phrase the question in this slightly roundabout way.
– realityChemist
Aug 2 at 11:42
@realityChemist : Oh, so 'free edge' is like what is called a 'flag' in some contexts. Actually, I un-retract my previous comment. Havel-Hakimi should give you what you want. Given a degree sequence like [3, 3, 3, 3, 2, 2] it gives you the connectivity of a graph if one can be constructed.
– gilleain
Aug 2 at 12:39
add a comment |Â
up vote
1
down vote
favorite
up vote
1
down vote
favorite
Say I have two types of vertices:
- (D) vertices have two edges
- (T) vertices have three edges
Given a collection of these vertices, is there any way to prove whether they can be joined edge-to-edge to form a closed (i.e. no free edges) graph in 3-space?
For example, say I have 3 (T) vertices and 1 (D) vertex. (Unless I've missed something obvious) there is no way to join these vertices into a closed graph in space, but I'm not able to come up with a proof. On the other hand, 4 (T) vertices and 0 (D) vertices form a simple tetrahedron.
What about higher-order examples, such as 12 (T) vertices and 4 (D) vertices? Ideally I would like to be able to construct an example of a graph in cases where they exist, at least for small collections like these, but this isn't tagged for constructive-mathematics because I don't consider construction an absolute requirement.
graph-theory 3d
asked Aug 1 at 20:40
realityChemist
1585
Say I have two types of vertices:
- (D) vertices have two edges
- (T) vertices have three edges
Given a collection of these vertices, is there any way to prove whether they can be joined edge-to-edge to form a closed (i.e. no free edges) graph in 3-space?
For example, say I have 3 (T) vertices and 1 (D) vertex. (Unless I've missed something obvious) there is no way to join these vertices into a closed graph in space, but I'm not able to come up with a proof. On the other hand, 4 (T) vertices and 0 (D) vertices form a simple tetrahedron.
What about higher-order examples, such as 12 (T) vertices and 4 (D) vertices? Ideally I would like to be able to construct an example of a graph in cases where they exist, at least for small collections like these, but this isn't tagged for constructive-mathematics because I don't consider construction an absolute requirement.
graph-theory 3d
asked Aug 1 at 20:40
realityChemist
1585
asked Aug 1 at 20:40
realityChemist
1585
asked Aug 1 at 20:40
realityChemist
1585
asked Aug 1 at 20:40
realityChemist
1585
1585
Where does 3-space come in? And what exactly is a free edge? Are you wondering if it is possible to construct a graph with a given number of D and T vertices?
– Morgan Rodgers
Aug 2 at 6:47
3-space comes in because these graphs represent something in the real world, although I guess the question is mathematically equivalent to the 2-D case as long as you allow edges to cross. And by "free edge" I mean an edge that's only connected to a vertex at one end. I think that because of the way graphs and edges are defined your rephrasing is equivalent and would be a more standard way to think about the question. The real-world analog is what lead me to phrase the question in this slightly roundabout way.
– realityChemist
Aug 2 at 11:42
@realityChemist : Oh, so 'free edge' is like what is called a 'flag' in some contexts. Actually, I un-retract my previous comment. Havel-Hakimi should give you what you want. Given a degree sequence like [3, 3, 3, 3, 2, 2] it gives you the connectivity of a graph if one can be constructed.
– gilleain
Aug 2 at 12:39
add a comment |Â
Where does 3-space come in? And what exactly is a free edge? Are you wondering if it is possible to construct a graph with a given number of D and T vertices?
– Morgan Rodgers
Aug 2 at 6:47
3-space comes in because these graphs represent something in the real world, although I guess the question is mathematically equivalent to the 2-D case as long as you allow edges to cross. And by "free edge" I mean an edge that's only connected to a vertex at one end. I think that because of the way graphs and edges are defined your rephrasing is equivalent and would be a more standard way to think about the question. The real-world analog is what lead me to phrase the question in this slightly roundabout way.
– realityChemist
Aug 2 at 11:42
@realityChemist : Oh, so 'free edge' is like what is called a 'flag' in some contexts. Actually, I un-retract my previous comment. Havel-Hakimi should give you what you want. Given a degree sequence like [3, 3, 3, 3, 2, 2] it gives you the connectivity of a graph if one can be constructed.
– gilleain
Aug 2 at 12:39
Where does 3-space come in? And what exactly is a free edge? Are you wondering if it is possible to construct a graph with a given number of D and T vertices?
– Morgan Rodgers
Aug 2 at 6:47
Where does 3-space come in? And what exactly is a free edge? Are you wondering if it is possible to construct a graph with a given number of D and T vertices?
– Morgan Rodgers
Aug 2 at 6:47
3-space comes in because these graphs represent something in the real world, although I guess the question is mathematically equivalent to the 2-D case as long as you allow edges to cross. And by "free edge" I mean an edge that's only connected to a vertex at one end. I think that because of the way graphs and edges are defined your rephrasing is equivalent and would be a more standard way to think about the question. The real-world analog is what lead me to phrase the question in this slightly roundabout way.
– realityChemist
Aug 2 at 11:42
3-space comes in because these graphs represent something in the real world, although I guess the question is mathematically equivalent to the 2-D case as long as you allow edges to cross. And by "free edge" I mean an edge that's only connected to a vertex at one end. I think that because of the way graphs and edges are defined your rephrasing is equivalent and would be a more standard way to think about the question. The real-world analog is what lead me to phrase the question in this slightly roundabout way.
– realityChemist
Aug 2 at 11:42
@realityChemist : Oh, so 'free edge' is like what is called a 'flag' in some contexts. Actually, I un-retract my previous comment. Havel-Hakimi should give you what you want. Given a degree sequence like [3, 3, 3, 3, 2, 2] it gives you the connectivity of a graph if one can be constructed.
– gilleain
Aug 2 at 12:39
@realityChemist : Oh, so 'free edge' is like what is called a 'flag' in some contexts. Actually, I un-retract my previous comment. Havel-Hakimi should give you what you want. Given a degree sequence like [3, 3, 3, 3, 2, 2] it gives you the connectivity of a graph if one can be constructed.
– gilleain
Aug 2 at 12:39
add a comment |Â
1 Answer
1
active
oldest
votes
up vote
2
down vote
Claim: A graph comprised of exactly $t$ vertices of degree $3$ and $d$ vertices of degree $2$ and no other vertices exists if and only if the following conditions are met:
- $t$ is even
- $t+dgeq 4$
or
- $t=0,d=3$
A sketch of an proof:
The condition that $t$ must be even is seen immediately from the handshaking lemma. That $t=0,d=3$ works is seen from the example $K_3$. That no other graphs with less than four vertices works is obvious.
What remains is to show that every other can be created. We do this by induction. $K_4$, $C_4$, and the diamond graph $K_4-e$ work as examples for base cases.
Given a graph with $t$ vertices of degree three and $d$ vertices of degree $2$, we may increase the number of vertices of degree $2$ by one by replacing any edge $u,v$ with two new edges and a vertex between them: $u,x,x,v$, as pictured below:
becomes:
For increasing the number of vertices of degree $3$ by two, we may take any two distinct edges and replace them both like above with the additional step of connecting the two newly created vertices, as pictured below:
becomes
(Note: we merely require the edges be distinct, but they may share a vertex if desired. They cannot share two vertices since otherwise the edges would not have been distinct in the first place.)
It should be clear that the newly created graphs using either of these modifications will be a graph with the desired number of vertices of degree $3$ and $2$ and the degrees of the vertices from the original graph are unchanged by the process.
It follows by induction then that every choice of $t,d$ possible where $t$ is even and $t+dgeq 4$ leads to the construction of a graph with $t$ vertices of degree $3$ and $d$ vertices of degree $2$ with no other vertices.
As an example of the ideas above being put into action, you ask about $d=4,t=12$. The following graph was created using $C_4$ as a base, and repeatedly applying the modifications described in the induction argument. (you can even see exactly the order in which they were applied if you note how the vertices are labeled, since I just used the default names for the vertices as they were created)
This is of course not the only example of a graph with $d=4$ and $t=12$ but it should hopefully highlight how such a construction could occur.
answered Aug 1 at 22:03
JMoravitz
44k33481
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
add a comment |Â
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
2
down vote
Claim: A graph comprised of exactly $t$ vertices of degree $3$ and $d$ vertices of degree $2$ and no other vertices exists if and only if the following conditions are met:
- $t$ is even
- $t+dgeq 4$
or
- $t=0,d=3$
A sketch of an proof:
The condition that $t$ must be even is seen immediately from the handshaking lemma. That $t=0,d=3$ works is seen from the example $K_3$. That no other graphs with less than four vertices works is obvious.
What remains is to show that every other can be created. We do this by induction. $K_4$, $C_4$, and the diamond graph $K_4-e$ work as examples for base cases.
Given a graph with $t$ vertices of degree three and $d$ vertices of degree $2$, we may increase the number of vertices of degree $2$ by one by replacing any edge $u,v$ with two new edges and a vertex between them: $u,x,x,v$, as pictured below:
becomes:
For increasing the number of vertices of degree $3$ by two, we may take any two distinct edges and replace them both like above with the additional step of connecting the two newly created vertices, as pictured below:
becomes
(Note: we merely require the edges be distinct, but they may share a vertex if desired. They cannot share two vertices since otherwise the edges would not have been distinct in the first place.)
It should be clear that the newly created graphs using either of these modifications will be a graph with the desired number of vertices of degree $3$ and $2$ and the degrees of the vertices from the original graph are unchanged by the process.
It follows by induction then that every choice of $t,d$ possible where $t$ is even and $t+dgeq 4$ leads to the construction of a graph with $t$ vertices of degree $3$ and $d$ vertices of degree $2$ with no other vertices.
As an example of the ideas above being put into action, you ask about $d=4,t=12$. The following graph was created using $C_4$ as a base, and repeatedly applying the modifications described in the induction argument. (you can even see exactly the order in which they were applied if you note how the vertices are labeled, since I just used the default names for the vertices as they were created)
This is of course not the only example of a graph with $d=4$ and $t=12$ but it should hopefully highlight how such a construction could occur.
answered Aug 1 at 22:03
JMoravitz
44k33481
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
add a comment |Â
up vote
2
down vote
Claim: A graph comprised of exactly $t$ vertices of degree $3$ and $d$ vertices of degree $2$ and no other vertices exists if and only if the following conditions are met:
- $t$ is even
- $t+dgeq 4$
or
- $t=0,d=3$
A sketch of an proof:
The condition that $t$ must be even is seen immediately from the handshaking lemma. That $t=0,d=3$ works is seen from the example $K_3$. That no other graphs with less than four vertices works is obvious.
What remains is to show that every other can be created. We do this by induction. $K_4$, $C_4$, and the diamond graph $K_4-e$ work as examples for base cases.
Given a graph with $t$ vertices of degree three and $d$ vertices of degree $2$, we may increase the number of vertices of degree $2$ by one by replacing any edge $u,v$ with two new edges and a vertex between them: $u,x,x,v$, as pictured below:
becomes:
For increasing the number of vertices of degree $3$ by two, we may take any two distinct edges and replace them both like above with the additional step of connecting the two newly created vertices, as pictured below:
becomes
(Note: we merely require the edges be distinct, but they may share a vertex if desired. They cannot share two vertices since otherwise the edges would not have been distinct in the first place.)
It should be clear that the newly created graphs using either of these modifications will be a graph with the desired number of vertices of degree $3$ and $2$ and the degrees of the vertices from the original graph are unchanged by the process.
It follows by induction then that every choice of $t,d$ possible where $t$ is even and $t+dgeq 4$ leads to the construction of a graph with $t$ vertices of degree $3$ and $d$ vertices of degree $2$ with no other vertices.
As an example of the ideas above being put into action, you ask about $d=4,t=12$. The following graph was created using $C_4$ as a base, and repeatedly applying the modifications described in the induction argument. (you can even see exactly the order in which they were applied if you note how the vertices are labeled, since I just used the default names for the vertices as they were created)
This is of course not the only example of a graph with $d=4$ and $t=12$ but it should hopefully highlight how such a construction could occur.
answered Aug 1 at 22:03
JMoravitz
44k33481
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
add a comment |Â
up vote
2
down vote
up vote
2
down vote
Claim: A graph comprised of exactly $t$ vertices of degree $3$ and $d$ vertices of degree $2$ and no other vertices exists if and only if the following conditions are met:
- $t$ is even
- $t+dgeq 4$
or
- $t=0,d=3$
A sketch of an proof:
The condition that $t$ must be even is seen immediately from the handshaking lemma. That $t=0,d=3$ works is seen from the example $K_3$. That no other graphs with less than four vertices works is obvious.
What remains is to show that every other can be created. We do this by induction. $K_4$, $C_4$, and the diamond graph $K_4-e$ work as examples for base cases.
Given a graph with $t$ vertices of degree three and $d$ vertices of degree $2$, we may increase the number of vertices of degree $2$ by one by replacing any edge $u,v$ with two new edges and a vertex between them: $u,x,x,v$, as pictured below:
becomes:
For increasing the number of vertices of degree $3$ by two, we may take any two distinct edges and replace them both like above with the additional step of connecting the two newly created vertices, as pictured below:
becomes
(Note: we merely require the edges be distinct, but they may share a vertex if desired. They cannot share two vertices since otherwise the edges would not have been distinct in the first place.)
It should be clear that the newly created graphs using either of these modifications will be a graph with the desired number of vertices of degree $3$ and $2$ and the degrees of the vertices from the original graph are unchanged by the process.
It follows by induction then that every choice of $t,d$ possible where $t$ is even and $t+dgeq 4$ leads to the construction of a graph with $t$ vertices of degree $3$ and $d$ vertices of degree $2$ with no other vertices.
As an example of the ideas above being put into action, you ask about $d=4,t=12$. The following graph was created using $C_4$ as a base, and repeatedly applying the modifications described in the induction argument. (you can even see exactly the order in which they were applied if you note how the vertices are labeled, since I just used the default names for the vertices as they were created)
This is of course not the only example of a graph with $d=4$ and $t=12$ but it should hopefully highlight how such a construction could occur.
answered Aug 1 at 22:03
JMoravitz
44k33481
Claim: A graph comprised of exactly $t$ vertices of degree $3$ and $d$ vertices of degree $2$ and no other vertices exists if and only if the following conditions are met:
- $t$ is even
- $t+dgeq 4$
or
- $t=0,d=3$
A sketch of an proof:
The condition that $t$ must be even is seen immediately from the handshaking lemma. That $t=0,d=3$ works is seen from the example $K_3$. That no other graphs with less than four vertices works is obvious.
What remains is to show that every other can be created. We do this by induction. $K_4$, $C_4$, and the diamond graph $K_4-e$ work as examples for base cases.
Given a graph with $t$ vertices of degree three and $d$ vertices of degree $2$, we may increase the number of vertices of degree $2$ by one by replacing any edge $u,v$ with two new edges and a vertex between them: $u,x,x,v$, as pictured below:
becomes:
For increasing the number of vertices of degree $3$ by two, we may take any two distinct edges and replace them both like above with the additional step of connecting the two newly created vertices, as pictured below:
becomes
(Note: we merely require the edges be distinct, but they may share a vertex if desired. They cannot share two vertices since otherwise the edges would not have been distinct in the first place.)
It should be clear that the newly created graphs using either of these modifications will be a graph with the desired number of vertices of degree $3$ and $2$ and the degrees of the vertices from the original graph are unchanged by the process.
It follows by induction then that every choice of $t,d$ possible where $t$ is even and $t+dgeq 4$ leads to the construction of a graph with $t$ vertices of degree $3$ and $d$ vertices of degree $2$ with no other vertices.
As an example of the ideas above being put into action, you ask about $d=4,t=12$. The following graph was created using $C_4$ as a base, and repeatedly applying the modifications described in the induction argument. (you can even see exactly the order in which they were applied if you note how the vertices are labeled, since I just used the default names for the vertices as they were created)
This is of course not the only example of a graph with $d=4$ and $t=12$ but it should hopefully highlight how such a construction could occur.
answered Aug 1 at 22:03
JMoravitz
44k33481
edited Aug 2 at 23:51
answered Aug 1 at 22:03
JMoravitz
44k33481
answered Aug 1 at 22:03
JMoravitz
44k33481
answered Aug 1 at 22:03
JMoravitz
44k33481
44k33481
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
add a comment |Â
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
Upon closer inspection, the condition that the two edges in the induction step for increasing $t$ must not share any vertices is unnecessary. Any choice of two distinct edges suffices. As an aside, through careful wording, one can even show that not only can such a graph exist, but you can even show that such a graph can be both planar (drawable in 2d with no crossing edges) and connected as well.
– JMoravitz
Aug 2 at 23:49
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
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2869499%2fclosed-graph-from-a-collection-of-vertices%23new-answer', 'question_page');
);
Post as a guest
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
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
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
Where does 3-space come in? And what exactly is a free edge? Are you wondering if it is possible to construct a graph with a given number of D and T vertices?
– Morgan Rodgers
Aug 2 at 6:47
3-space comes in because these graphs represent something in the real world, although I guess the question is mathematically equivalent to the 2-D case as long as you allow edges to cross. And by "free edge" I mean an edge that's only connected to a vertex at one end. I think that because of the way graphs and edges are defined your rephrasing is equivalent and would be a more standard way to think about the question. The real-world analog is what lead me to phrase the question in this slightly roundabout way.
– realityChemist
Aug 2 at 11:42
@realityChemist : Oh, so 'free edge' is like what is called a 'flag' in some contexts. Actually, I un-retract my previous comment. Havel-Hakimi should give you what you want. Given a degree sequence like [3, 3, 3, 3, 2, 2] it gives you the connectivity of a graph if one can be constructed.
– gilleain
Aug 2 at 12:39