# Spatial graphs and their chromatic number

## Main Question or Discussion Point

Suppose a generalization of planar graph is considered into 3D space :

a graph is said "spatial" if it can be constructed in Euclidean 3D space in such a way that no edge intersects a face.

The questions are the following :

-as for plane graphs their chromatic number is 4, can we show that the chromatic number for spatial graphs is 5 since K5 is spatial but not K6. (Kn is the complete n-vertices graph)

-If we consider a further generalization, can it be shown that Kn is "constructible" in a n-2 dimensional space such that no edge intersects any n-1-hyperface, but not K(n+1) ?

Last edited:

What exactly do you mean by a "face"?

Consider, for example, a 4-cycle where the vertices do not lie in a plane. What does it mean for an edge to intersect that face?

chiro
Is a face just the equivalent of a subset of the surface formed in n-dimensions?

For the 4-cycle, it's any surface whose boundary is that cycle.
The edges involved in defining the boundary can of course not intersect the surface, it would have been edges from other vertices.

I think I can add that : every cycle which has no sub-cycle spans such a surface which is called a face.

Last edited:
For the 4-cycle, it's any surface whose boundary is that cycle.
The edges involved in defining the boundary can of course not intersect the surface, it would have been edges from other vertices.

I think I can add that : every cycle which has no sub-cycle spans such a surface which is called a face.
OK, in that case, please explain why you think K6 can't be embedded in 3-space in this way.

Simply because else you should have an edge that interesect one of the faces :

It simple to construct K5 in that way : take a tetrahedron and put a vertice in the center of it, then link to every vertex of the tetrahedron.

Note now that the interior of the tetrahedron is divided by the faces into 4 smaller tetrahedron.

If you try to build K6 either you put your vertex in one of these smaller tetrahedron, which makes the opposite vertex inaccessible (since a face cannot intersect with an edge), if you put your 6th vertice exterior to the bigger tetrahedron, then the inner 5th point can't be reached.

Office_Shredder
Staff Emeritus
Gold Member
What is your precise definition of a face if your graph isn't planar to begin with?

Simply because else you should have an edge that interesect one of the faces :

It simple to construct K5 in that way : take a tetrahedron and put a vertice in the center of it, then link to every vertex of the tetrahedron.

Note now that the interior of the tetrahedron is divided by the faces into 4 smaller tetrahedron.

If you try to build K6 either you put your vertex in one of these smaller tetrahedron, which makes the opposite vertex inaccessible (since a face cannot intersect with an edge), if you put your 6th vertice exterior to the bigger tetrahedron, then the inner 5th point can't be reached.
OK, so you have discovered a way to construct K6 that does not meet the requirements. But you have not proved that there is no way to construct K6 that meets the requirements.

EDIT: I should explain what problem you will encounter. If you try to formalize this argument into a proof, there will come a time when you have to say that if you take 4 vertices, connect them with edges, and then for every cycle, put a surface whose boundary is that cycle, then the resulting object has an inside and an outside. That is not clear to me.

In fact, I don't believe it is true.

Last edited:
Office_Shredder
Staff Emeritus
Gold Member
OK, so you have discovered a way to construct K6 that does not meet the requirements. But you have not proved that there is no way to construct K6 that meets the requirements.

EDIT: I should explain what problem you will encounter. If you try to formalize this argument into a proof, there will come a time when you have to say that if you take 4 vertices, connect them with edges, and then for every cycle, put a surface whose boundary is that cycle, then the resulting object has an inside and an outside. That is not clear to me.

In fact, I don't believe it is true.
There's only four vertices, if it isn't true you should be able to construct a counterexample :tongue:. The inside is the convex hull of those vertices - they form a tetrahedron (unless they're coplanar).

Only if the surfaces are flat.

If two of the surfaces are cross-caps then you have a Klein bottle, and there is no longer an inside or outside.

The real question is whether this difficulty can be dismissed by insisting that the surfaces be non-self-intersecting.

I don't see really good in space what you mean, but Klein bottle has no boundary, however the cycle has to be the boundary of the surface.

If we take non minimal surfaces they shall not intersect edges, i think it's a sufficient condition in order to see topologically that one vertex in K5 is "locked in" ?

I don't think to add the condition the surfaces cannot intersect another surface is necessary if you ask they already don't intersect with edges, in order to see that K6 is not makeable.

But one thing is sure, I don't have the skills to formalize that. Already the definition of a spatial graph is not clear (maybe you have litterature advice on this)

Last edited:
Office_Shredder
Staff Emeritus