1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Spatial graphs and their chromatic number

  1. Oct 11, 2013 #1
    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: Oct 11, 2013
  2. jcsd
  3. Oct 13, 2013 #2
    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?
  4. Oct 13, 2013 #3


    User Avatar
    Science Advisor

    Is a face just the equivalent of a subset of the surface formed in n-dimensions?
  5. Oct 13, 2013 #4
    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: Oct 13, 2013
  6. Oct 15, 2013 #5
    OK, in that case, please explain why you think K6 can't be embedded in 3-space in this way.
  7. Oct 15, 2013 #6
    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.
  8. Oct 15, 2013 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    What is your precise definition of a face if your graph isn't planar to begin with?
  9. Oct 15, 2013 #8
    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: Oct 15, 2013
  10. Oct 15, 2013 #9


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    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).
  11. Oct 15, 2013 #10
    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.
  12. Oct 16, 2013 #11
    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: Oct 16, 2013
  13. Oct 16, 2013 #12


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    I'm still not sure what the definition of a face is supposed to be if you have a cycle of more than three vertices which are not coplanar.
  14. Oct 16, 2013 #13
    Mathematically I supposed this can be any smooth surface which has the edges as boundary (the edges can be curves), but there I'm maybe missing some points.

    Physically one can imagine a soap film hanging at the edges, hence a minimal surface.

    I think the problem arise because we are used to see faces as plane, but we could imagine any smooth deformation of them, as long as they don't intersect other edges.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook