Return to Question

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

I wonder if some construction like Steiner system may be useful for constructing a counterexample. On the other hand, if the answer is positive, the circling method is likely not straightforward: simple ideas like choosing $1$ from $\{1,2\}$, $2$ from $\{2,3\}$, and $3$ from $\{1,3\}$ do not seem to work.

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

I wonder if some construction like Steiner system may be useful for constructing a counterexample.

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

I wonder if some construction like Steiner system may be useful for constructing a counterexample. On the other hand, if the answer is positive, the circling method is likely not straightforward: simple ideas like choosing $1$ from $\{1,2\}$, $2$ from $\{2,3\}$, and $3$ from $\{1,3\}$ do not seem to work.

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

Let $k$ vertices in a graph be given. Some pairs of vertices are connected by an edge, each edge is labeled either $\{1,2\}$, $\{1,3\}$, or $\{2,3\}$. We can circle some of the numbers on the edges. If an edge is $\{1,2\}$, some vertex adjacent to it must be adjacent to a circled $1$ and a circled $2$. A similar requirement holds for $\{1,3\}$ and $\{2,3\}$ edges. Is it true that for any graph and labels, it is sufficient to circle at most $\lceil 3k/2\rceil$ numbers?

For instance, if $k = 3$ and the three edges have label $\{1,2\}$, $\{1,3\}$, $\{2,3\}$, then it suffices to circle the first $1$, the first $3$, and the second $2$. It seems that $\lceil 3k/2\rceil$ numbers suffice in other examples as well. Is something known about this or similar problems?

I wonder if some construction like Steiner system may be useful for constructing a counterexample.