6 9 1 3 1 5 2 5 2 6 3 4 3 5 3 6 4 6 5 6
No No No No Yes No No Yes Yes Consider the case where edge $(4,6)$ is removed. A spanning tree formed by edges $(1,3),(2,5),(3,4),(3,5),(5,6)$ satisfies the condition. For example, for edge $(3,6)$, the simple path connecting vertices $3$ and $6$ traverses vertices $3,5,6$ in this order, and the minimum and maximum vertex numbers on the path are $3$ and $6$, respectively, thus satisfying the condition. By verifying the other edges similarly, it can be seen that this spanning tree satisfies the condition, so the answer is `Yes`. On the other hand, consider the case where edge $(1,5)$ is removed. The same spanning tree does not satisfy the condition. For edge $(4,6)$, the simple path connecting vertices $4$ and $6$ traverses vertices $4,3,5,6$ in this order, and the minimum and maximum vertex numbers on the path are $3$ and $6$, respectively, thus not satisfying the condition. It can also be shown that no other spanning tree satisfies the condition, so the answer is `No`.
5 4 1 2 2 3 3 4 4 5
No No No No Removing an edge may disconnect the graph.
15 20 12 13 7 8 5 7 8 10 9 12 4 5 11 12 2 4 6 8 4 14 1 2 14 15 2 9 3 8 2 15 10 11 13 14 8 9 7 14 5 13
No No No Yes Yes No Yes No No No No No No No No Yes No No No No
{
"problem": {
"name": "Min and Max at the edge",
"description": {
"content": "An undirected graph with numbered vertices is called a **good graph** if it has a spanning tree $T$ that satisfies the following condition. Here, an edge connecting two vertices $u$ and $v$ $(u < v)$ ",
"description_type": "Markdown"
},
"platform": "AtCoder",
"limit": {
"time_limit": 3000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "arc181_e"
},
"statements": [
{
"statement_type": "Markdown",
"content": "An undirected graph with numbered vertices is called a **good graph** if it has a spanning tree $T$ that satisfies the following condition. Here, an edge connecting two vertices $u$ and $v$ $(u < v)$ ...",
"is_translate": false,
"language": "English"
}
]
}