3
$\begingroup$

I'm struggling to prove the following:

Edges of a connected cubic graph G can be colored with 3 colors in such a way that no adjacent edges are of the same color. 2 edges were removed from the graph making it disconnected. Proof that those edges were of the same color.

I've found an example of a cubic graph with two edges that disconnect it, and tried to color them with different colors and failed to do that, but I'm not sure how to prove that.

example of a graph

$\endgroup$

1 Answer 1

Reset to default
3
$\begingroup$

Proceed by contradiction. Let $H$ be $G$ after removing the two edges.

Take a connected component $C$ of $H$ and assume $e$ is a removed edge from a vertex $x$ in $C$ to a vertex not in $C$.

Also assume $e$ is blue and the other removed edge is green.

Let the other color be red. Note that the red edges with endings in $C$ form a matching of $C$ so $|C|$ is even.

On the other hand the blue edges with endings in $C$ form a matching of $C\setminus \{x\}$ so $|C|-1$ is even.

A contradiction.

$\endgroup$
3
  • $\begingroup$ By $C∖{x}$ do you mean $C - x$ (graph induced by $C∖{x}$)? $\endgroup$
    – Ellie
    Apr 18, 2022 at 1:50
  • $\begingroup$ @Ellie yeah, I used the "setminus" latex thingy, which means the same thing :) $\endgroup$
    – Asinomás
    Apr 18, 2022 at 8:51
  • $\begingroup$ Ok, thank you. Also, great solution! $\endgroup$
    – Ellie
    Apr 18, 2022 at 10:20

You must log in to answer this question.

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