0
$\begingroup$

This just seems way to simple to me to be able to put into words. Essentially what I want to say is that since we know that we are able to hit all the vertices in the graph without hitting any of the edges/vertices more than one, removing one of the edges means that we are removing an edge that is only traversed once. Since the edge was only traversed once, we know that removing it still allows for all the vertices to be walked to from any other vertex. Any help on how to strengthen this argument would be really appreciated :)

$\endgroup$
0
$\begingroup$

Suppose we have a proper cycle with vetex set $V=\{ v_i \mid i=1,2, \cdots ,n \}$ and edge set $E= \{ e_{i,i+1} =(v_i,v_{i+1} \mid i=1,\cdots,n-1 \} \cup \{e_{n,1} =(v_n,v_1) \}$. Now suppose one of these edges is removed, can you write down a path from any pair of vertices ?

Further hint : Assume we remove the edge $e_{i,i+1}$, a path from $v_j$ to $v_k$ where $j \leq i$ and $i+1 \leq k$ can be constructed by $ v_j e_{j,j-1} v_{j-1} \cdots v_0 e_{0,n} v_n e_{n,n-1} \cdots v_k $.

There are other cases that need to shown but to write out the path explicitly is quite easy.

$\endgroup$
  • $\begingroup$ Yeah, you can. I'm just not sure how to necessarily prove that you can. $\endgroup$ – Mathperson12345 Nov 21 '17 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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