4
$\begingroup$

I have the following the statement and I have to prove whether it is true or not.

Given a planar and Hamiltonian graph $\mathbb{G} = (V, E)$, show that we can partition $E = E_1 \cup E_2 = E$ so that $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ are both connected and outerplanar graphs.

I have tested the statement for few graphs and it seems correct to me, but I am not sure how can I use the property of the Hamiltonian cycle to decompose the graph into two sub-graphs.

I appreciate any hint!

Improve this question
$\endgroup$
  • 1
    $\begingroup$ What is the connection between $\mathbb{V},\mathbb{E},V,E_1,E_2$? $\endgroup$ – Yuval Filmus Nov 3 '20 at 14:20
  • $\begingroup$ Sorry, I have just edited the post $\endgroup$ – Mohbenay Nov 3 '20 at 14:27
  • 1
    $\begingroup$ Can you find a connected non-Hamiltonian planar graph for which this fails? $\endgroup$ – Yuval Filmus Nov 3 '20 at 14:43

Your Answer

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

Browse other questions tagged or ask your own question.