# Does such a graph exist? [closed]

[EDITED FOR CLARITY]

Does there exist an edge-colored graph $$G$$ with the following properties?

1. $$G$$ has a vertex $$r$$ with exactly three, distinctly colored, incident edges: $$(r, u)$$, $$(r, v)$$, $$(r, w)$$.

2. Every properly colored$$^*$$ spanning tree $$T$$ of $$G$$ has one of the following two types:

A: $$~T$$ includes edge $$(r, u)$$ but neither $$(r, v)$$ nor $$(r, w)$$, or

B: $$~T$$ includes edges $$(r, v)$$ and $$(r, w)$$ but not $$(r, u)$$.

3. $$G$$ has at least one properly colored spanning tree of each of these two types.

$$^*$$(Properly colored means no two incident edges in $$T$$ have the same color.)

Here is an example of a graph $$G$$ that meets every condition except the third (it has just one properly colored connected spanning tree, of type B):

Here is an example of a graph $$G$$ where $$r$$ has two incident edges, and meets the analogous conditions for those two edges (there are properly colored spanning trees with edge $$(r, u)$$ but not $$(r, w)$$, or with $$(r, w)$$ but not $$(r, u)$$, and every properly colored spanning tree has exactly one of those two edges):

• I added the definition, $a, b, c$ are for the convenience of me to express clearly, not label. Dec 3, 2021 at 6:10
• This is still not clear to me. Are you talking about every possible valid edge-colouring of every possible spanning tree? or is the graph firstly edge-coloured and you are talking about every spanning tree of that edge-coloured graph? Are you saying that you want a graph which contains one vertex like this $r$ ?
– JimN
Dec 3, 2021 at 7:14
• I want an edge-colored graph which contains one vertex like this $r$. Dec 3, 2021 at 7:19
• I agree with @NealYoung that it still seems that the colours 1,2,3 play no role in this
– JimN
Dec 3, 2021 at 7:26
• The graph is an edge-colored graph, $a,b,c$ with color $1,2,3$, resp. That means $a,b,c$ has different colors. Dec 3, 2021 at 7:47

EDIT: The answers below are for previous versions of the question.

[This version asked for an edge-colored graph $$G$$ with a vertex $$r$$ such that has exactly three edges $$a,b,c$$, with colors $$1,2,3$$, and such that $$G$$ has at least two properly colored spanning trees $$T_1$$ and $$T_2$$ such that $$T_1$$ has $$a$$ and not $$b$$ or $$c$$, and $$T_2$$ has $$b$$ and $$c$$ but not $$a$$.]

Take $$G=(V, E)$$ where $$V=\{r, u, v, w\}$$ and $$E=\{(r, u), (r, v), (r, w), (u, v), (v, w)\}$$ with edges $$(r, u)$$, $$(v, w)$$ colored 1, edges $$(r, w)$$ and $$(u, v)$$ colored 3, and edge $$(r, v)$$ colored 2.

Then take $$T_1$$ to have edges $$(r, v)$$, $$(r, w)$$, $$(u, v)$$. Take $$T_2$$ to have edges $$(r, u)$$, $$(u, v)$$, $$(v, w)$$.

[The version asked for an edge-colored graph $$G$$ with a vertex $$r$$ with incident edges $$a$$, $$b$$, and $$c$$, each of a different color, that has at least one properly colored spanning tree, and such that every properly colored spanning tree had either edge $$a$$ (and not $$b$$ or $$c$$) or edges $$b$$ and $$c$$ (but not $$a$$).]

Take $$G=(V, E)$$ where $$V=\{r, u, v, w, s\}$$ and $$E=\{(r, u), (r, v), (r, w), (u, v), (u, s)\}$$ with edges $$(r, u)$$, $$(u, s)$$ colored 1, edges $$(r, w)$$ and $$(u, v)$$ colored 3, and edge $$(r, v)$$ colored 2. (See the picture below.)

Then the tree $$T$$ with edges $$(r, v)$$, $$(r, w)$$, $$(u, s)$$, $$(u, v)$$ form a properly colored spanning tree with edges $$b=(r, v)$$ and $$c=(r, w)$$ but not $$a=(r, u)$$. Also, this is the only properly colored spanning tree.

[This version asked for an edge-colored graph $$G$$ with a vertex $$r$$ with incident edges $$a$$, $$b$$, and $$c$$, each of a different color, such that every properly colored spanning tree had either edge $$a$$ (and not $$b$$ or $$c$$) or edges $$b$$ and $$c$$ (but not $$a$$).]
Take $$G=(V, E)$$ where $$V=\{r, u, v, w, s\}$$ and $$E=\{(r, u), (r, v), (r, w), (u, s)\}$$ with edges $$(r, u)$$, $$(u, s)$$ colored 1, edge $$(r, w)$$ colored 3, and edge $$(r, v)$$ colored 2.
• I need that for every properly colored spanning trees $T$ in $G$, either $T$ has $a$ and not $b,c$ or has $b,c$ but not $a$. Dec 7, 2021 at 6:07