1
$\begingroup$

Consider a connected graph of $n\ge 7$ vertices. The edges are colored in two colors, and for each vertex, there is equal number of edges of each color connected to it. There is also a vertex with 6 edges connected to it.

Is it true that in this graph, there exists a cycle that alternates between the two colors?

$\endgroup$
  • 1
    $\begingroup$ I don't have enough time to run the full test, but I would assume yes, since: When $n=7$ it is obviously true, since every node needs at least $2$ edges that have different colors and hence one finds such a cycle. If $n > 7$ then only the case is interesting where there is no such cycle with only using the node with $6$ edges and its neighbors. You have to show that in that case you find an alternating path between two neighbors that are connected to the one with $6$ edges with an edge of the same color. $\endgroup$ – RoyPJ Nov 6 '17 at 12:26
  • 1
    $\begingroup$ My previous comment assumes that a cycle (red - blue - red) is indeed alternating (although it could also be read as (red - red - blue). If that doesn't count, then the proposition is obviously not true, because only cycles with even numbers could possibly be alternating. One can easily construct a graph with $n=7$ nodes that has no cycle with even length. $\endgroup$ – RoyPJ Nov 6 '17 at 12:28
1
$\begingroup$

The properties of the graph assure that we can start from a vertex $v$ of degree six and go along the edges, in each vertex choosing the next edge to go which was not passed before and is colored differently to the color of the incoming edge, until we reach the vertex $v$ again. Denote the cycle (not necessarily simple) which we just passed as $C_1$ and remove all its edges from the graph. Again start from the vertex $v$ and go along the remaining edges according to the previous rules, until we reach the vertex $v$ again. Denote the cycle (not necessarily simple) which we just passed as $C_2$. Repeat the above process again, obtaining a cycle $C_3$. The construction of the cycles $C_i$ assures that each vertex of $C_i$ different from $v$ is incident to differently colored edges of $C_i$. If in each of the cycles $C_i$ the vertex $v$ is incident to similarly colored edges of $C_i$ then the vertex $v$ is incident in total to an even number of edges of each color, which is impossible, because this number is $3$. Thus there exists a cycle $C_i$ each vertex of which is incident to differently colored edges of $C_i$.

The following example shows that there may be no alternating cycle visiting each its vertex only once.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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