Partitioning edges/diagonals in subsets of three, originating from the same vertex

43 Views Asked by At

Clearer version: Is it possitle to partition the set of edges and diagonals of a 100-gon in subsets of three elements, originating from the same vertex?


I was wondering if there would be a simple way to know if for a n-gon, when inspecting its edges and diagonals, there is a way to color three edge/diagonals from each vertex with unique colors. For example, for a triangle there doesn't exist three edge/diagonals from a vertex, so the answer is impossible. For a square, it's also impossible because if you take three edge/diagonals from one vertex, then you can't get the remaining three lines to meet at another vertex. In a similar sense, a hexagon seems to work.

1

There are 1 best solutions below

0
On

If the partition can be done for $6n$, then it can be done for $6n+6$. Take a partition of the edge/diagonals of $K_{6n}$ and enhance it by adding the following: for each new vertex divide the edges going out of it to the $6n$ vertices of $K_{6n}$ into groups of 3. For the 15 edge/diagonals among the 6 new vertices, use the partition of $K_6$.

It follows that the partition exists for $K_{6n}$ by induction (since it exists for $K_6$. But then it exists for $K_{6n+1}$ as well. Simply partition the new edge/diagonals coming out of the additional vertex into the other 6n vertices in groups of 3.

It is not possible for $K_{6n+2}$ since the number of edge/diagonals is $(6n+2)(6n+1)/2$ which is not divisible by 3. Similarly it is not possible for $K_{6n+5}$.

The only cases remaining are $K_{6n+3}$ and $K_{6n+4}$. Note that again $K_{6n+4}$ follows from $K_{6n+3}$. For $K_{6n+3}$, we show the partition exists for $n\geq 1$. Take the partition for $k_{6n}$ and enhance it as follows. Choose one from the $6n$ vertices and connect it to the 3 new vertices. Then divide each of the remaining $6n+1$ edge/diagonals coming out of the 3 vertices into groups of 3 by including only 1 of the edge/diagonals connecting to the other three vertices.