-1
$\begingroup$

[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


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

$\endgroup$
9
  • $\begingroup$ I added the definition, $a, b, c$ are for the convenience of me to express clearly, not label. $\endgroup$
    – zhukui bai
    Dec 3 '21 at 6:10
  • 1
    $\begingroup$ 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$ ? $\endgroup$
    – JimN
    Dec 3 '21 at 7:14
  • $\begingroup$ I want an edge-colored graph which contains one vertex like this $r$. $\endgroup$
    – zhukui bai
    Dec 3 '21 at 7:19
  • $\begingroup$ I agree with @NealYoung that it still seems that the colours 1,2,3 play no role in this $\endgroup$
    – JimN
    Dec 3 '21 at 7:26
  • $\begingroup$ The graph is an edge-colored graph, $a,b,c$ with color $1,2,3$, resp. That means $a,b,c$ has different colors. $\endgroup$
    – zhukui bai
    Dec 3 '21 at 7:47
4
$\begingroup$

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



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.

$\endgroup$
5
  • $\begingroup$ I re-described the topic, it should be clear now. $\endgroup$
    – zhukui bai
    Dec 6 '21 at 3:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – Neal Young
    Dec 6 '21 at 16:29
  • $\begingroup$ 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$. $\endgroup$
    – zhukui bai
    Dec 7 '21 at 6:07
  • $\begingroup$ 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. $\endgroup$
    – Neal Young
    Dec 7 '21 at 12:59
  • $\begingroup$ Thank you very much. $\endgroup$
    – zhukui bai
    Dec 8 '21 at 7:14

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