Can a graph be non-planar in 3d?

A finite graph has a finite vertex set $V=\{v_1,v_2,\ldots, v_n\}$. Arrange these vertices as points $v_k=(k,0,0)$ $(1\leq k\leq n)$ on the $x$-axis of ${\mathbb R}^3$. Some pairs $v_i$, $v_j$ $(i\ne j)$ are joined by an edge. Assume there are $N\leq{n\choose2}$ edges. Choose $N$ different planes containing the $x$-axis, and draw each occurring edge $\{v_i,v_j\}$ as a half circle connecting $v_i$ with $v_j$ in one of these planes. The $N$ edges will then not intersect.

By the way: Graphs of functions and graphs studied here have nothing in common. It's a semantic accident that the two completely different things have obtained the same name.


To extend Christian's construction: you can in fact even embed the vertices of your graph in $\mathbb{R}^3$ so that all $N$ edges of the graph are straight lines, and this construction is close to trivial: just make all of the coordinates of the vertices algebraically independent of each other. You can show that this is possible by a dimensionality/counting argument (essentially, given any finite collection of real numbers, there are only countably many numbers in algebraic dependence with them, so there are uncountably many algebraically independent choices that can be made at each step). The key difference between space and the plane here is that while any two non-parallel straight lines will intersect in the plane, lines in space have an additional 'degree of freedom' that means that they need to satisfy certain conditions in order to intersect, and those conditions can be expressed algebraically in terms of the endpoints of segments of the two lines.

Tags:

Graph Theory

Planar Graphs

Related

Prove or disprove that $PQ = P + Q - I$ if $P$ and $Q$ are disjoint permutation matrices whose cycle lengths sum to $n.$ Find the properties of an ellipse from 5 points in 3D space Evaluate $\lim\limits_{n \to \infty}\frac{(-1)^n}{n!}\int_0^n (x-1)(x-2)\cdots(x-n){\rm d}x$ Prove that $\frac{(3 a+3 b) !(2 a) !(3 b) !(2 b) !}{(2 a+3 b) !(a+2 b) !(a+b) ! a !(b !)^{2}}$ is an integer. No. of positive integral solutions and link to coefficients in expansion What is the concrete meaning of fixing an extension field through a subgroup of automorphisms in $x^3-2$? Two permutation matrices represent conjugate permutations iff they have same characteristic polynomial. Prove that $\sqrt{x} > \ln x$ for all $x>0$ with a study of function Given any incomplete theory and an unprovable sentence $\varphi$, are there always strictly weaker consistent unprovable statements? How many times must a bounded random number generator bounded by its output run until it outputs 1? Evaluating $\int _0^1\frac{\ln \left(x^2+x+1\right)}{x\left(x+1\right)}\:dx$ $\lim_{n \to \infty} x_n = 0$ and $\lim_{n \to \infty} f(x_n) = a$

Recent Posts