I was given a full directed connected graph $G$ which it's edges are colored in two colors: red and blue.

I was asked to prove that the subgraph that contains all of the nodes and only one of the colored edges is connected (it can be weakly or strongly connected), but I got stuck in the process. Any help will do!


closed as off-topic by Morgan Rodgers, Xander Henderson, Saad, Shailesh, Leucippus Jun 2 '18 at 4:27

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – Xander Henderson, Saad, Shailesh, Leucippus
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ what do you mean by full directed graph? do you take all edges in all directions? $\endgroup$ – Yanko Jun 1 '18 at 19:57
  • $\begingroup$ Weakly or strongly connected? $\endgroup$ – Hagen von Eitzen Jun 1 '18 at 20:00
  • $\begingroup$ If this is a specific coloring of a specific directed graph ("full", I know, but how many vertices?), how can we help answer your question without knowing what the graph or the coloring is? $\endgroup$ – Morgan Rodgers Jun 1 '18 at 20:01
  • $\begingroup$ @HagenvonEitzen what do you mean by weakly? $\endgroup$ – Lola Jun 1 '18 at 20:02
  • $\begingroup$ @MorganRodgers The graph is a full graph- each node is connected to all of the others directly (with either a blue or a red edge) $\endgroup$ – Lola Jun 1 '18 at 20:04

Suppose the red subgraph is not strongly connected, i.e., there are two vertices $a,b$ such that there is no red path from $a$ to $b$. Then in paricular the edge $a\to b$ is blue. For any other vertex, at least one of $a\to c$, $c\to b$ is blue, hence $c$ is weakly connected to $a$ via blue edges: $c\to b\leftarrow a$ or $c\leftarrow a$. We conclude that the blue subgraph is weakly connected.

If we ask for strongly instead of weakly connected, this need not be the case: In $G$, pick any two vertices $a,b$, colour each edge staring in $a$ and/or ending in $b$ red and each edge starting in $b$ and/or ending in $a$ blue and colour all other edges arbitrarily. Then the red subgraph is not strongly connected because there is no red path $b\to\ldots \to a$, and the blue subgraph is not strongly connected because there is no blue path $a\to\ldots\to b$.

  • $\begingroup$ What is x exactly?:) $\endgroup$ – Lola Jun 1 '18 at 20:12
  • 1
    $\begingroup$ @Lola x is the key to the left of c on my keyboard :) $\endgroup$ – Hagen von Eitzen Jun 1 '18 at 20:15
  • $\begingroup$ Amazing! thank you very much :) $\endgroup$ – Lola Jun 1 '18 at 20:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.