0
$\begingroup$

As how concise the title is, my question is: why can't two colors disconnect a complete graph?

This problem originates from this codeforces problem: Train splitting, which roughly translates as "color the edges of the graph such that":

  1. The graph with one color is no longer connected.
  2. The graph with two colors must be connected.

It should be clear that if we do not have a complete graph, just pick that one vertex that is not adjecent to all other vertices and then color all of its adjecent edges with one color and the rest of the edges with another color. Two colors should be enough. The real problem kicks in with a complete graph, for which these two questions come to my mind naturally:

  1. What prevents me from using two colors to achieve condition 1? Or, why can't two colors disconnect a complete graph?($K_3$ is such a case).
  2. How does 3 colors help me with that? The author of the problem suggests that we should "for all adjecent edges of each vertex, color any two edges with two colors and the rest with a third color". I'm not sure why this is the case. Here's the link: solution in page 11

Thank you for reading. Your help would be a lot to me :D

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $K_n$ be the complete graph on $n$ vertices, labelled by the integers $[n]=\{1,2,3\ldots n\}$.

We shall show that it is not possible to color each edge of $K_n$ with one of two colors, say red and blue, such that each of the edge-subgraphs consisting of all the edges of one color are disconnected.

Towards a contradiction, assume that we can do that, and that the red and blue edge-subgraphs are both disconnected.

Then, there must exist 2 vertices which are contained in different components of the blue-subgraph. Let these vertices be $x$ and $y$. Since the blue-subgraph disconnects them we may deduce the following:

  1. The edge $xy$ is red.
  2. For any $v\neq x,y$, it must have at least one of the edges $vx$ or $vy$ colored red, for otherwise there is the entirely blue path $xvy$ connecting $x$ and $y$.

We use these two facts to show that the red-subgraph now must be connected.

Let $W\subseteq V$ be the component of the red-subgraph that contains $x$. By the first item, it must contain $y$ as well. By the second item, it must contain all $v\neq x,y$ as well. Thus the red-subgraph is connected, whence we obtain a contradiction to the fact that both color subgraphs are disconnected.


Here is an explicit construction with 3 colors, for $K_7$ but generalizes readily to $K_n$.3-Coloring for K_7 (I apologise for the crude drawing.)

This construction is motivated by the idea that in the proof above, the second item results in the red-subgraph becoming connected. In order to combat this I uniformly color all $vx$ edges blue and all $vy$ edges green. Coloring the rest red just works.

$\endgroup$
3
  • $\begingroup$ Thanks for the answer. But I'm not sure if your proof's objective is quite correct "We shall show that it is not possible to color each edge of Kn with one of two colors, say red and blue, such that each of the edge-subgraphs consisting of all the edges of one color are disconnected.". It requires only one of the edge-subgraphs to be disconnected. I'm sorry if the question is not clear :(. $\endgroup$ Commented Jul 27, 2023 at 4:45
  • 1
    $\begingroup$ "For any company, there should exist two cities such that it is impossible to reach one from the other using only routes operated by that company." - Looking at this part of the Codeforces problem, I think it requires that each subgraph(the set of all routes operated by one company) be disconnected. Further, if you only needed one subgraph to be disconnected, you could make each edge red, whence the blue subgraph is trivially disconnected having $n$ distinct components. $\endgroup$ Commented Jul 27, 2023 at 5:09
  • $\begingroup$ Thanks. Clever proof! A colored graph to be connected if and only if it "includes" all vertices of the graph :D. I didn't think of this. $\endgroup$ Commented Jul 27, 2023 at 6:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .