<p><em>EDIT: The answers below are for previous versions of the question.</em></p>
<p><strong>Answer for third version:</strong></p>
<p>[<em>This version asked for an edge-colored graph <span class="math-container">$G$</span> with a vertex <span class="math-container">$r$</span> such that has exactly three edges <span class="math-container">$a,b,c$</span>, with colors <span class="math-container">$1,2,3$</span>, and such that <span class="math-container">$G$</span> has at least two properly colored spanning trees <span class="math-container">$T_1$</span> and <span class="math-container">$T_2$</span> such that <span class="math-container">$T_1$</span> has <span class="math-container">$a$</span> and not <span class="math-container">$b$</span> or <span class="math-container">$c$</span>, and <span class="math-container">$T_2$</span> has <span class="math-container">$b$</span> and <span class="math-container">$c$</span> but not <span class="math-container">$a$</span>.</em>]</p>
<p>Take <span class="math-container">$G=(V, E)$</span> where <span class="math-container">$V=\{r, u, v, w\}$</span> and <span class="math-container">$E=\{(r, u), (r, v), (r, w), (u, v), (v, w)\}$</span> with edges <span class="math-container">$(r, u)$</span>, <span class="math-container">$(v, w)$</span> colored 1, edges <span class="math-container">$(r, w)$</span> and <span class="math-container">$(u, v)$</span> colored 3, and edge <span class="math-container">$(r, v)$</span> colored 2.</p>
<p>Then take <span class="math-container">$T_1$</span> to have edges <span class="math-container">$(r, v)$</span>, <span class="math-container">$(r, w)$</span>, <span class="math-container">$(u, v)$</span>.
Take <span class="math-container">$T_2$</span> to have edges <span class="math-container">$(r, u)$</span>, <span class="math-container">$(u, v)$</span>, <span class="math-container">$(v, w)$</span>.</p>
<hr />
<hr />
<p><strong>Answer for second version:</strong></p>
<p><em>[The version asked for an edge-colored graph <span class="math-container">$G$</span> with a vertex <span class="math-container">$r$</span> with incident edges <span class="math-container">$a$</span>, <span class="math-container">$b$</span>, and <span class="math-container">$c$</span>, 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 <span class="math-container">$a$</span> (and not <span class="math-container">$b$</span> or <span class="math-container">$c$</span>) or edges <span class="math-container">$b$</span> and <span class="math-container">$c$</span> (but not <span class="math-container">$a$</span>).]</em></p>
<p>Take <span class="math-container">$G=(V, E)$</span> where <span class="math-container">$V=\{r, u, v, w, s\}$</span> and <span class="math-container">$E=\{(r, u), (r, v), (r, w), (u, v), (u, s)\}$</span> with edges <span class="math-container">$(r, u)$</span>, <span class="math-container">$(u, s)$</span> colored 1, edges <span class="math-container">$(r, w)$</span> and <span class="math-container">$(u, v)$</span> colored 3, and edge <span class="math-container">$(r, v)$</span> colored 2. (See the picture below.)</p>
<p>Then the tree <span class="math-container">$T$</span> with edges <span class="math-container">$(r, v)$</span>, <span class="math-container">$(r, w)$</span>, <span class="math-container">$(u, s)$</span>, <span class="math-container">$(u, v)$</span> form a properly colored spanning tree with edges <span class="math-container">$b=(r, v)$</span> and <span class="math-container">$c=(r, w)$</span> but not <span class="math-container">$a=(r, u)$</span>.  Also, this is the only properly colored spanning tree.</p>
<p><a href="https://i.sstatic.net/1KzvUm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/1KzvUm.png" alt="enter image description here" /></a></p>
<hr />
<hr />
<p><strong>Answer for first version:</strong></p>
<p><em>[This version asked for an edge-colored graph <span class="math-container">$G$</span> with a vertex <span class="math-container">$r$</span> with incident edges <span class="math-container">$a$</span>, <span class="math-container">$b$</span>, and <span class="math-container">$c$</span>, each of a different color, such that every properly colored spanning tree had either edge <span class="math-container">$a$</span> (and not <span class="math-container">$b$</span> or <span class="math-container">$c$</span>) or edges <span class="math-container">$b$</span> and <span class="math-container">$c$</span> (but not <span class="math-container">$a$</span>).]</em></p>
<p>Take <span class="math-container">$G=(V, E)$</span> where <span class="math-container">$V=\{r, u, v, w, s\}$</span> and <span class="math-container">$E=\{(r, u), (r, v), (r, w), (u, s)\}$</span> with edges <span class="math-container">$(r, u)$</span>, <span class="math-container">$(u, s)$</span> colored 1, edge <span class="math-container">$(r, w)$</span> colored 3, and edge <span class="math-container">$(r, v)$</span> colored 2.</p>
<p>This graph has no properly colored spanning tree, so trivially satisfies the given condition.</p>

CC BY-SA 4.0
2021-12-06T03:27:12.240Z
I re-described the topic, it should be clear now.
Yuhang Bai
CC BY-SA 4.0
2021-12-06T16:29:03.280Z
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.
Neal Young
CC BY-SA 4.0
2021-12-07T06:07:40.447Z
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$.
Yuhang Bai
CC BY-SA 4.0
2021-12-07T12:59:09.613Z
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.
Neal Young
CC BY-SA 4.0
2021-12-08T07:14:23.863Z
Thank you very much.
Yuhang Bai
CC BY-SA 4.0
2021-12-05T13:56:31.440Z
2021-12-07T13:52:16.917Z
2021-12-07T13:52:16.917Z
Neal Young
<p><em>[EDITED FOR CLARITY]</em></p>
<p>Does there exist an edge-colored graph <span class="math-container">$G$</span> with the following properties?</p>
<ol>
<li><p><span class="math-container">$G$</span> has a vertex <span class="math-container">$r$</span> with exactly three, distinctly colored, incident edges: <span class="math-container">$(r, u)$</span>, <span class="math-container">$(r, v)$</span>, <span class="math-container">$(r, w)$</span>.</p>
</li>
<li><p>Every <em>properly colored</em><span class="math-container">$^*$</span> spanning tree <span class="math-container">$T$</span> of <span class="math-container">$G$</span> has one of the following two types:</p>
<p>A: <span class="math-container">$~T$</span> includes edge <span class="math-container">$(r, u)$</span> but neither <span class="math-container">$(r, v)$</span> nor <span class="math-container">$(r, w)$</span>, or</p>
<p>B: <span class="math-container">$~T$</span> includes edges <span class="math-container">$(r, v)$</span> and <span class="math-container">$(r, w)$</span> but not <span class="math-container">$(r, u)$</span>.</p>
</li>
<li><p><span class="math-container">$G$</span> has at least one properly colored spanning tree of each of these two types.</p>
</li>
</ol>
<p><span class="math-container">$^*$</span>(<em>Properly colored</em> means no two incident edges in <span class="math-container">$T$</span> have the same color.)</p>
<hr />
<p>Here is an example of a graph <span class="math-container">$G$</span> that meets every condition except the third (it has just one properly colored connected spanning tree, of type B):
<a href="https://i.sstatic.net/EmLiPm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/EmLiPm.png" alt="enter image description here" /></a></p>
<hr />
<p>Here is an example of a graph <span class="math-container">$G$</span> where <span class="math-container">$r$</span> has <em>two</em> incident edges, and meets the analogous conditions for those two edges (there are properly colored spanning trees with edge <span class="math-container">$(r, u)$</span> but not <span class="math-container">$(r, w)$</span>, or with <span class="math-container">$(r, w)$</span> but not <span class="math-container">$(r, u)$</span>, and every properly colored spanning tree has exactly one of those two edges):</p>
<p><a href="https://i.sstatic.net/pBhQVm.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/pBhQVm.png" alt="enter image description here" /></a></p>

CC BY-SA 4.0
2021-12-03T06:10:08.913Z
I added the definition, $a, b, c$ are for the convenience of me to express clearly, not label.
Yuhang Bai
CC BY-SA 4.0
2021-12-03T07:14:00.743Z
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
CC BY-SA 4.0
2021-12-03T07:19:42.090Z
I want an edge-colored graph which contains one vertex like this $r$.
Yuhang Bai
CC BY-SA 4.0
2021-12-03T07:26:10.523Z
I agree with @NealYoung that it still seems that the colours 1,2,3 play no role in this
JimN
CC BY-SA 4.0
2021-12-03T07:47:11.487Z
The graph is an edge-colored graph, $a,b,c$ with color $1,2,3$, resp. That means $a,b,c$ has different colors.
Yuhang Bai
CC BY-SA 4.0
2021-12-03T20:53:05.330Z
Is this a correct statement of your problem?  You want a graph $G$, an assignment of a color to each edge of $G$, and a vertex $r$ of $G$, with the following properties: (i) $r$ has three edges in $G$ (call them $a$, $b$, $c$), having distinct colors (call them 1, 2, and 3) and (ii) in any spanning tree $T$ of $G$, if, in each pair of incident edges in $T$, the two edges have different colors, then either $T$ has edge $a$ but not edge $b$ or $c$, OR $T$ has edges $b$ and $c$ but not $a$.  Is this right?
Neal Young
CC BY-SA 4.0
2021-12-04T02:26:10.800Z
Your statement is correst. However, i need $G$ has a properly colored spanning tree.
Yuhang Bai
CC BY-SA 4.0
2021-12-04T17:53:01.823Z
[BTW I suggest editing your question to make the problem statement clear. You're welcome to use my restatement of your problem (adding the additional conditions e.g. that there is such a tree) if you want.]
Neal Young
CC BY-SA 4.0
2021-12-05T13:03:49.043Z
Thank you. I do.
Yuhang Bai
<graph-theory><graph-algorithms><reductions>
Does such a graph exist?
Yuhang Bai
# Does such a graph exist?

(Asked by: username_0 on 2021-12-02)

*[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):
[![enter image description here](https://i.sstatic.net/EmLiPm.png)](https://i.sstatic.net/EmLiPm.png)

---

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):

[![enter image description here](https://i.sstatic.net/pBhQVm.png)](https://i.sstatic.net/pBhQVm.png)

**Tags:** graph-theory, graph-algorithms, reductions
> **Comments:**
> **username_0**: I added the definition, $a, b, c$ are for the convenience of me to express clearly, not label.  
> **username_1**: 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$ ?  
> **username_0**: I want an edge-colored graph which contains one vertex like this $r$.  
> **username_1**: I agree with @NealYoung that it still seems that the colours 1,2,3 play no role in this  
> **username_0**: The graph is an edge-colored graph, $a,b,c$ with color $1,2,3$, resp. That means $a,b,c$ has different colors.  
> **username_2**: Is this a correct statement of your problem?  You want a graph $G$, an assignment of a color to each edge of $G$, and a vertex $r$ of $G$, with the following properties: (i) $r$ has three edges in $G$ (call them $a$, $b$, $c$), having distinct colors (call them 1, 2, and 3) and (ii) in any spanning tree $T$ of $G$, if, in each pair of incident edges in $T$, the two edges have different colors, then either $T$ has edge $a$ but not edge $b$ or $c$, OR $T$ has edges $b$ and $c$ but not $a$.  Is this right?  
> **username_0**: Your statement is correst. However, i need $G$ has a properly colored spanning tree.  
> **username_2**: [BTW I suggest editing your question to make the problem statement clear. You're welcome to use my restatement of your problem (adding the additional conditions e.g. that there is such a tree) if you want.]  
> **username_0**: Thank you. I do.  

---

## 1 answers

### Answer by username_2 on 2021-12-05. Score: 4

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

[![enter image description here](https://i.sstatic.net/1KzvUm.png)](https://i.sstatic.net/1KzvUm.png)

---

---

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

> **Comments:**
> **username_0**: I re-described the topic, it should be clear now.  
> **username_2**: 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.  
> **username_0**: 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$.  
> **username_2**: 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.  
> **username_0**: Thank you very much.  

---

