Several $good$ points, several $bad$ points and several segments are drawn in the plane. Each segment connects a $good$ point and a $bad$ one; at most $100$ segments begin at each point. We have paint of $200$ colors. One half of each segment is painted with one of these colors, and the other half with another one. Is it always possible to do it so that every two segments with common end are painted with four different colors? (M. Qi, X. Zhang)
Problem
Source: Tuymaada 2022 Junior P-4
Tags: graph theory, Coloring
01.07.2023 20:39
Yeah. We define the bipartite graph $T$ so that its vertices and edges correspond to the (good and bad) points and segments in the problem. We denote its parts by $V_1$ and $V_2.$ We need also the graph $T',$ a copy of $T.$ For each vertex $A$ of $T$ the corresponding vertex of $T'$ is denoted by $A',$ the parts of $T'$ are $V'_1$ and $V'_2.$ The union of $T$ and $T'$ is a bipartite graph; we will consider the union of $V_1$ and $V'_2$ as one part and the union of $V_2$ and $V'_1$ as another part of this graph. If a vertex $A$ in $T$ has degree $d < 100,$ the vertex $A'$ lies in the other part and has the same degree. We can add $100 - d$ edges between $A$ and $A'$ and repeat this procedure until we get a bipartite graph $Q$ such that $T$ is its subgraph and all the vertices of $Q$ have degree $100.$ The graph $Q$ is regular (that is, all its vertices have the same degree). Thus we have constructed a regular graph. This graph can have multiple edges; the reader is advised to check that our argument is not affected by it. We need the following well-known Hall’s theorem. If a bipartite graph $G$ satisfies Hall’s condition, then $G$ contains a set $R$ of edges such that each vertex of $G$ is the end of exactly one edge in $R.$ Such a set is called a perfect matching in $G.$ The Hall’s condition requires that for each $k$ and each $k$ vertices belonging to the same part of $G,$ the number of vertices adjacent to them is at least $k.$ Let us check the Hall’s condition for the graph $Q.$ If for $k$ vertices in one part there are only $l < k$ vertices adjacent to them, the edges between these vertices have exactly $100k$ ends in one part and at most $100l < 100k$ vertices in another part, a contradiction. Thus $Q$ admits a perfect matching. We can color all the edges of this matching with the first color and remove them from $Q.$ A regular graph remains with vertices of degree $99.$ In this graph we can again find a perfect matching, color its edges with the second color and remove them. Repeating this operation $100$ times (we like simple monotonous work) we color all the edges of $Q$ with $100$ colors so that all the edges beginning in each vertex have different colors. Such coloring is called edge coloring of $Q.$ Since $T$ is a subgraph of $Q,$ it also admits an edge coloring with $100$ colors. It remains to split each color $s$ into two hues $s_1$ and $s_2$ and color two halves of each edge of color s with different hues $s_1$ and $s_2.$