Proof of the third scene (f) in 22 years

F topic
The question ： Given an undirected graph , Ask two points each time x, y, Ask whether there is one n Permutation , Make the first element x, The last element is y, And any prefix of the arrangement 、 Any suffix is connected .
solution
（ I found that I can't order double , Quickly get started with graph theory 555
It's not hard to think of something related to cutting points , But only part of it qaq
This question should start with a bit of dual nature
Disorderly classification and discussion
If uv Double at the same point , Bipartite property , Deleting any point can keep the connection , So direct yes.
If uv At different points, double , And a total of two points are double and adjacent .（ Let's not consider the disconnected situation ）.
It is also possible to construct permutations $p_1{p}_2...pn$ Of , among $p\mathrm{1..}pi$ Belong to a dot double ,$p_{i+1}...pn$ Belong to another ,$u=p_1,v=p_n$
If there are more pairs, consider how to construct , After using double shrinking points , It's a tree . because uv Must be at the beginning and end of the array , This tree must be in the form of a chain ,uv The point pair must be at the beginning and end of the chain . The conclusion feels good .
The counter evidence method randomly proves that this tree is a chain ：
Suppose it's not a chain , There are at least three leaves , set up uv The dot pairs are U,V(U≠V), The other leaf is T. Might as well set U And T Of lca by LCA, We will first UV Path construction to permutation p in ,
$p_1...p_{i}The\; corresponding\; isU->LCAPoints\; on\; this\; path\; are\; double$, $p_{i+1}...p_{n}The\; corresponding\; isU->LCAPoints\; on\; this\; path\; are\; double$,（ Omission does not mean a series of consecutive subscripts ）
There is still T->LCA The dot pairs on this path are not added to the arrangement , Consider if there is only T and LCA Two points , How to construct .
Because a point may belong to multiple point pairs at the same time , Suppose dot double LCA Middle link U, Connect T The point of （LCA,U,T It's a set of points ！） Belong to at the same time LCA,U and T（ But when shrinking, it can only be temporarily placed in a set , Let's say that now LCA This collection ）, Because this situation can increase the connectivity between point pairs , Thus, it is easier to construct the arrangement （ Poor expression qaq）, We set this key point as k spot .

Now? U To V This path has been placed in the arrangement , Consider joining T. Consider keeping the prefixes of the permutation connected , The best way is to join k after , Just put T In the point , hypothesis k There's one in the back T In the point q, Let's look at the permutation suffix , Suffix at this time V To T The paths are disconnected , because k stay q front ！！！
Then the reasoning to the worse case can not be constructed ！
Certificate completion

If uv If the dot pair is at the beginning and end , We need to make a special judgment uv It's the case of cutting points . After all, the above can only guarantee the construction of uv Separate arrangement , And make sure that uv Connectivity between .
Pay attention to special judgment n=2 The situation of , Always be yes.