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.
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:
or
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+d\geq 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.