for n in range (1, n):
for j in range(1, n+1):
k = 1
while k <= j:
k *= 42

This is a HW question. The conditions seem to be talking about a cycle graph (they are 2 connected and have vertices of degree 2). For them the condition checks out. But I don't know for sure it refers to them.

My next thought was to try a proof by contradiction. So we assume u is not on one the paths.It has to be part of V(G) since the graph is 2 connected. I feel like the degree is significant, but I don't know where to go. Do we say something like u has to be connected to some vertices on some of the paths, making it part? How do I prove that claim? Am I totally wrong?

EDIT: enter image description here

This seems to be a solution that disproves the thing. It is 2 connected and the deg(u) is 2. It's also not on any ear decomp path because if you go to u, you end up in another one. Is this allowed, since we restrict the Paths themselves?

  • $\begingroup$ It looks to me like the graph in your picture has an ear decomposition $P_0,P_1,P_2,P_3$ with $u$ on $P_3$ where $P_3$ is the path of length $2$ with $u$ in the middle. Why am I wrong? $\endgroup$
    – bof
    Oct 9, 2020 at 4:09
  • $\begingroup$ I'm a little confused by the whole concept to be honest. Ear decomposition is basically internally disjoint paths between 2 vertices from what I understood. I could create ear decomp that does not have u but don't know if it is valid. $\endgroup$
    – pasha
    Oct 9, 2020 at 11:08


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.