Induct on number of vertices.Base case $n=2$ is easy.Now,it is well known that if we have a connected graph $G$ with more than one vertex,there exists a vertex $v$ such that $G/v$ is connected(consider a spanning tree and remove a leaf).Now,pick a vertex $v$ such that $G/v$ is connected.By inductive hypothesis,there exists a coloring/marking of $G/v$.Now,vertex $v$ has at least one edge. Case 1:$v$ has no adjacent vertices among green vertices. Color $v$ green and mark all its edges. Case $2$:It has at least one adjacent vertex among green vertices. Color it blue and mark only edges with green vertices.

khina wrote:

Wait does it? I don't understand the first process. Consider a triangle $A - B - C$ and an extra vertex $D$ which only connects to $C$. By your algorithm, if we start from $D$(start from any vertex), we would color $C$ black, and both $A$ and $B$ being green, which is not allowed.

GorgonMathDota wrote: khina wrote:

Wait does it? I don't understand the first process. Consider a triangle $A - B - C$ and an extra vertex $D$ which only connects to $C$. By your algorithm, if we start from $D$(start from any vertex), we would color $C$ black, and both $A$ and $B$ being green, which is not allowed. So I think khina's explanation wasn't entirely clear, but I also got the same general idea of him and think it does work. Basically, you only add one green at a time, and every time you add a green you make sure that you make all of it's neighbors blue, before you add another green vertex. So for your example, we make D green, then C blue. Then we pick a neighbor of a blue vertex (in this case only C works), WLOG choose A, and make A green. Then we make all neighbors of A blue (in this case C, which is already blue, and more importantly make B blue), and are done.

I LOVE USING INDUCTION ON GRAPH THEORY PROBLEMS We induct on the number of vertices, with the base case of $1$ vertex being obvious. Now, we add a vertex $v$ and join a number of edges to it. If all vertices joined to $v$ are of one color, color $v$ with the opposite color and all of the edges black. Otherwise, color $v$ blue. There exists at least one green vertex adjacent to $v$, so we can draw a black edge connecting $v$ to that green vertex. Color the other edges white, which is allowable. In either case, there's a black edge connecting $v$ to some pre-existing vertex, which by hypothesis is connected to the rest of the graph, so we're done. $\blacksquare$

OK Let $n$ be number of vertices in $G$. Induct on $n$. Base case is clear. For the induction step, let $T$ be a spanning tree of $G$. Let $v$ be a leaf of $T$. Then $T - v$ is tree, so $G' = G - v$ is connected. Thus by inductive hypothesis, we can color vertices and edges that satisfies the problem condition. Let $v_{1}, v_{2}, \dots, v_{k}$ be neighbors of $v$ in $G$. If there exist $i$ such that $v_{i}$ is green, then color $v$ blue and color the edges $(v, v_{i})$ black and for all $j \neq i$, color the edge $(v, v_{j})$ white. Then there exist black spanning tree in $G$ and black edges join vertices of different colors and white edges have at least one blue endpoint. So assume for all $i$, $v_{i}$ is blue. Then color $v$ green and for all $i$, color the edge $(v, v_{i})$ black. Then there exist black spanning tree in $G$ and black edges join vertices of different colors and white edges have at least one blue endpoint. Thus we're done. $\blacksquare$

We use induction, starting with a trivial base case. The idea is to show that we can always color a spanning tree of the graph black by forming an algorithm of adding vertices. First note that all $G_{n+1}$ are obtainable from $G_n$ graphs, as there exists a vertex which can be deleted and perserve connectedness. Take a vertex of $G_{n+1}$ with this property. If this vertex is connected to some green vertex, we can color our vertex blue. Otherwise, we color our vertex green. Thus we are always able to connect this vertex to our black spanning tree. $\blacksquare$

We will prove this using induction. The base case of one point is vacuous. Suppose there is a graph such that the given conditions hold on $n$ vertices. Add a new vertex $v$. If each of the adjacent points to $v$ is the same color, color $v$ the opposite and every edge connected to $v$ is black. If else, color it blue, and at least one of the adjacent vertices must be green, creating a black edge, connecting $v$ to the rest of the graph in the subgraph containing only the black edges. $\square$

We will proceed with induction. $n=1$ works, assume $n=k$ works for all connected graph $G_k$. Now pick any such graph $G$, we will add a vertex $v$ to it and it can be connected in any way. If $v$ is connected to all green vertices, we will color it blue and color all its edges black. If $v$ is connected to all blue vertices we will color it green and color all its edges black. If $v$ is connected to a mix of green and blue vertices, we will color it blue and color its edges black as often as we could while coloring the rest white. The first two cases clearly satisfy the rules since we can just extend the original black paths. In the last case, we can ignore all the black edges we added as they are extending original paths and focus only on the new white edges. If an edge is white, by our algorithm we know it connects $v$ to a green vertex $u$. We know that $v$ will have at least one black edge incident to it, suppose that is connecting to $u'$. Then, we know that $uu'$ has a black path, and we can append the black edge to it to make a black path $uv$, circumventing the white edge.