I am struggling with how to approach this problem, specifically part a. What is the relationship between the length l of the longest open path and the sum of the degrees of any two non-adjacent vertices, and how does that help solve the problem?

$G$ is a simple connected graph with 20 vertices. Assume that for any two non-adjacent vertices $x$ and $y$ we have $deg(x) + deg(y)\geq 12.$

a) Let $x_1-x_2-...-x_l$ be the longest open path in $G$ (recall that in a path we have distinct vertices and distinct edges). If $l < 20$ then could ${x_1, x_l}$ be an edge of $G$? Prove your assertion.

b) Prove that $G$ has a cycle of length at least 7.


For part a) you can present a case where the longest open path is less than $20$ and does not make a circuit and make an argument that such a longest path not containing all vertices cannot be connected into a circuit.

The first case is relatively easy; have a $K_{12}$ component and then have one of the vertices connect individual edges to the other $8$ vertices not in the $K_{12}$. The longest path is $13$ and cannot be connected.

enter image description here

Now consider for the sake of contradiction a longest path $<20$ length which can be formed into a circuit. Then there are vertices not on the circuit, and because the graph is connected, there must be some such vertex $v$ adjacent to some point on the circuit. Then a longer path can be made by starting at $v$ and then following the circuit - contradiction. Therefore if the longest path does not include all nodes, it cannot be connected into a circuit.

  • $\begingroup$ That makes sense! Thank you. For part b, isn't it essentially asking whether $x_1, x_7$ could be an edge of G? It seems like it's asking for a proof of the same thing that was just disproven for part a. $\endgroup$ – fs24 Sep 6 '17 at 6:12
  • $\begingroup$ No, there's no sense in which the cycle of 7 must be the longest path so not the same. For that one I would expect the condition on vertex degree sum to be important. $\endgroup$ – Joffan Sep 6 '17 at 13:04
  • $\begingroup$ Certainly it is possible, for part (b), to construct a graph meeting the conditions where the maximum cycle is $7$ by connecting a $K_7, K_6, K_6$ suitably through a cut vertex. $\endgroup$ – Joffan Sep 6 '17 at 13:46

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.