What is the definition for k-line-connectedness of the graph ? I am in doubt whether it differs from usual k-vertex (edge) connectedness. I've encountered it in the paper titled "Np-complete problems on a 3-connected cubic planar graph and their applications" where it comes without definition. Unfortunately for me I couldn't get the definition from the context given in its authors' proofs.


Judging from the proof of Lemma 1 in the paper, 3-line-connected is the same as 3-edge-connected; line is probably a translation from Japanese.

  • $\begingroup$ Unfortunately with 3-edge-connectedness Lemma 1 proof is wrong. $\endgroup$ – KKS Jan 14 '16 at 13:13
  • $\begingroup$ You can find an alternative proof here: homepages.math.uic.edu/~mubayi/591/Spring2010/hw3sol.pdf. $\endgroup$ – Yuval Filmus Jan 14 '16 at 13:19
  • $\begingroup$ This is OK now. Thanks. Let me wait a bit to get final check for this answer. :-) $\endgroup$ – KKS Jan 14 '16 at 14:19
  • $\begingroup$ After the second reading I get that this Japanese paper contains wrong proofs. That's sad. Not only for 3-connectedness = 3-edge-connectedness statement but also for main results. $\endgroup$ – KKS Jan 14 '16 at 16:35
  • $\begingroup$ For example, for completeness of VC when replacing the 1-disconnecting edges the situation could happen when the gadget is adjacent to at least two gadgets. In this case obtained graph is not cubic, $\endgroup$ – KKS Jan 15 '16 at 15:38

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.