For convenience rename the points $P_1,...,P_n$. We will proceed by induction on $n$, starting from $n=6$. By induction, it easy to see that we can construct by adding $P_{i+1}$ (if necessary relabel the points so that we have the right order) outside of the convex hull of $P_1...P_i$. So we may assume $P_n$ is outside the convex hull of $P_1...P_{n-1}$ [name this convex hull $\mathcal{P}$ for convenience. Since $P_n$ is outside $\mathcal{P}$ there exist at least two points (say $P_1,P_2$) such that the segments $P_1P_n$ and $P_2P_n$ which don't intersect $\mathcal{P}$. If there also exists a third such point $P_3$, simply add one of these three segments to each of the three networks. Otherwise, assume wlog that road network $G_1$ didn't have $P_1P_2$ as a road. Now, consider the process of smoothly rotating the ray $P_nP_1$ to the ray $P_nP_2$ (passing through every other vertex in the process). Let wlog $P_3$ be (one of) the vertex connected to $P_1$ inside $G_1$ (by hypothesis this point couldn't have been $P_2$). If $P_nP_3$ is uninterrupted by other roads in $G_1$, just add this segment. Otherwise, in the process of rotation, let $P_4$ be first "obstacle" to seeing segment $P_1P_3$. It is clear to see that adding point $P_nP_4$ will work, as there can't be any ther obstacle (since $P_4$ was the first and no tree points are aligned). Now, since $P_nP_1$,$P_nP_2$, and $P_nP_4$ are distinct, we can just add these three to $G_2,G_3,G_1$ respectively, and we are done. So it suffices to check $n=6$ which has just a finite amount of cases.

So can anyone give an explicit proof of the base case when $n=6$?

cadaeibf wrote: Since $P_n$ is outside $\mathcal{P}$ there exist at least two points (say $P_1,P_2$) such that the segments $P_1P_n$ and $P_2P_n$ which don't intersect $\mathcal{P}$. If there also exists a third such point $P_3$, simply add one of these three segments to each of the three networks. But why are you sure the new networks will be still connected? I do not understand this problem! I mean, the way I got it it's too easy. First you connect the points to obtain a planar connected graph that spans all $n$ points. After that a spanning tree $T$ can be constructed. It represents the network $G_1$. Further, we take an edge $e_1$ of $T$ that is incident to a leaf of $T$, remove $e_1$ from $G_1$ (and $T$) and add it to $G_2$. Then, we take another edge $e_2\in T$ like that and this will be $G_3$. We remove $e_2$ from $G_1$. That is, $G_2$ and $G_3$ both consist of only one edge and all three of them are connected. That's it! To do this we need $n\ge 4$. P.S. If the point is to construct three disjoint spanning trees, it's not true that we can do it. Simply because a planar graph with $n$ vertices can have maximum $3n-6$ edges, so three spanning trees of $n-1$ edges each ..., no way to be edge disjoint. But, if one wants two spanning trees, it can be done as shown here.

dgrozev wrote: cadaeibf wrote: Since $P_n$ is outside $\mathcal{P}$ there exist at least two points (say $P_1,P_2$) such that the segments $P_1P_n$ and $P_2P_n$ which don't intersect $\mathcal{P}$. If there also exists a third such point $P_3$, simply add one of these three segments to each of the three networks. But why are you sure the new networks will be still connected? Simply because all of $P_1,P_2,P_3,P_4$ were part of the previous networks which were connected by induction hypothesis, and so the resulting networks are also connected

cadaeibf wrote: Simply because all of $P_1,P_2,P_3,P_4$ were part of the previous networks which were connected by induction hypothesis, and so the resulting networks are also connected I don't know what you are trying to prove!? If it is to show that there exists a planar graph on $x_1,\dots,x_n$ that can be decomposed into three edge-disjoint graphs, each one spanning all the vertices, then it is doomed - as shown in #4 it cannot be done. So, if you are trying to prove this, either the induction base is false, or your argument somewhere fails. If we drop the requirement each $G_i$ to span all the vertices, then you can simply add $P_nP_1$ into the network that passes through $P_1$ and you still keep each network connected. Or just proceed as in #4, there are many ways, this claim is trivial.

dgrozev wrote: P.S. If the point is to construct three disjoint spanning trees, it's not true that we can do it. Simply because a planar graph with $n$ vertices can have maximum $3n-6$ edges, so three spanning trees of $n-1$ edges each ..., no way to be edge disjoint. as shown here. Oh, the point is that the edges from two different networks don't have to be non intersecting. For example you may have 2 intersecting segments as long as they're in different networks. Therefore the union of the three networks need not to be a planar graph (which would have the described problem).

FloorX wrote: So can anyone give an explicit proof of the base case when $n=6$? I attach my base case; it deals all posible configurations by moving the points properly.

Attachments: