# The ends of the longest open path in a simple connected graph can be edges of the graph

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.

## 1 Answer

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. 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.

• 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. – fs24 Sep 6 '17 at 6:12
• 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. – Joffan Sep 6 '17 at 13:04
• 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. – Joffan Sep 6 '17 at 13:46