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

1 Answer

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

Answer for third version:

[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)$$.

Answer for second version:

[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.

Answer for first version:

[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.

This graph has no properly colored spanning tree, so trivially satisfies the given condition.

• I re-described the topic, it should be clear now. Dec 6, 2021 at 3:27
• I added an answer for your current version, although I expect your current version is also not what you intend to ask. Please make sure the wording of your question exactly captures what you intend to ask. Otherwise we will waste our time answering the wrong question. Dec 6, 2021 at 16:29
• 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
• Okay, meanwhile your question was closed for needing details or clarity. I've edited your question to hopefully address those issues. Let's see if it gets re-opened. Dec 7, 2021 at 12:59
• Thank you very much. Dec 8, 2021 at 7:14