# Vertex reachability in directed graph

In a directed graph, a vertex $$a$$ can reach every vertex, and every vertex can reach another vertex $$b$$. Can we always sort all the edges as $$e_1,e_2,\ldots,e_n$$ so that every prefix $$e_1,e_2,\dots,e_i$$ (when viewed as undirected edges) forms a connected subgraph, and similarly for every suffix $$e_i,e_{i+1},\dots,e_n$$?

I believe this is true if there is a path from $$a$$ to $$b$$ that contains all other vertices. Suppose the path is $$a\rightarrow v_1\rightarrow\dots\rightarrow v_k\rightarrow b$$. We let the edge $$a\rightarrow v_1$$ come first, then edges that connect $$v_2$$ to the set $$\{a,v_1\}$$ (in any order), then edges that connect $$v_3$$ to the set $$\{a,v_1,v_2\}$$, and so on. But is the statement true if there is no path from $$a$$ to $$b$$ that contains all other vertices?

• to put it in other way, your question is whether a certain sorting of edges has every sub-sorting as the edge set of a connected subgraph. And your argument shows it to be true for directed hamiltonian graphs Mar 2, 2019 at 10:39
• I think it is also true for eulerian graphs Mar 2, 2019 at 10:42

Add to $$G$$ a new edge $$e=\vec{ba}$$, the new graph $$G\cup e$$ is strongly connected. Start with a directed cycle containing $$e$$, let it consist of edges $$e_1,e_2,e_3,\dots,e_m,e$$, where $$e_1$$ is incident to $$a$$ and $$e_m$$ is incident to $$b$$. Start with a sequence $$e_1,e_2,\dots,e_m$$. Now I use an ear decomposition of $$G$$: the edge set $$E$$ is a disjoint union of $$E_1=\{e_1,e_2,\dots,e_m,e\}$$, $$E_2$$, $$E_3$$, $$\dots,E_s$$, where each $$E_i$$, $$i=2,3,\dots,s$$ is an ear: it is a set of edges of a simple directed path or cycle $$v_1 v_2\ldots v_r$$ in which all vertices except $$v_1$$ and $$v_r$$ are not covered by the set $$F_{i-1}:=E_1\cup\ldots\cup E_{i-1}$$ (while $$v_1$$ and $$v_r$$ are covered by $$F_{i-1}$$). The existence of an ear decomposition in a connected directed graph which starts from a given cycle is well known and easy to prove. So your conjecture follows by induction from the following
Lemma. Let $$H$$ be an undirected graph in which the edges are enumerated by $$e_1,\ldots,e_t$$ so that for all $$i=1,2,\ldots,t$$ the graphs formed by $$e_1,\ldots,e_i$$ and $$e_i,\ldots,e_t$$ are connected. Assume also that there are vertices $$a,b\in V(H)$$ such that $$a\in e_1,b\in e_t$$ and all other vertices of $$H$$ have degree at least 2. Let $$v_1\ldots v_r$$ be an ear for $$H$$, that is, a simple path or cycle with $$v_1,v_r\in V(H)$$ and $$v_2,\ldots,v_{r-1}$$ being new vertices. Then the graph $$H$$ plus this ear also has such an enumeration of edges.
Proof. If $$\{v_1,v_r\}\cap \{a,b\}\ne \emptyset$$, say $$v_r=b$$, add the edges $$v_1v_2,v_2v_3,\dots,v_{r-1}v_r$$ after $$e_t$$. Otherwise $$v_1,v_r$$ are not lists of $$H$$ and each of them is covered at least by two edges. Choose the minimal $$i$$ for which $$e_i$$ covers either $$v_1$$ or $$v_r$$. Without loss of generality $$v_1\in e_i$$. Then $$i and $$v_r$$ is covered by $$e_{i+1},\dots,e_t$$. Insert the edges $$v_1v_2,v_2v_3,\dots,v_{r-1}v_r$$ between $$e_i$$ and $$e_{i+1}$$.