an interest conjecture about the length of paths in a simple graph Let $G$ be a simple graph and let $A$ and $B$ be two different vertices of $G$. Suppose $P$ is a path between $A$ and $B$ in $G$ which satisfies the following:
For every vertex $u$ of $P$, there exists another vertex $v$ of $P$ and a vertex $C$ of $G$ which is not on $P$ such that $u$, $C$ and $v$, $C$ are both adjacent.
Then I conjecture that there must exist another path between $A$ and $B$ in $G$ which is longer than $P$. Is this true?
 A: I dont think that your statment is true .
There exist another path from $A$ to $B$ which is shorter or in the same length.
Let's look at the path $P:A=a_1\dots u.a_n\dots v,\dots a_m=B$(without lost of generality let v be closer to B).
So if i understand the question coerrctly there exist a path $S=a_1\dots u .c.v.a_k \dots a_m$ 
so the path is shorter if u and v are not adjacent.If they are than its true.
Edit :i just so that $G $ is asimple graph and if so ' you cannot make your assumption because then you will have a loop $u.c.v.a_k \dots a_n.u $ and if you dont assume that G is simple , i can give you a counter example(i dont write it now because it's hard to write graphs in latex)
Edit:
 
As you can see this graph setisfies your asumptions and the path $P=a_1,a_2,a_3,a_4$
$|P|=4$ and it is the maximal path (of course you canot repeat the same vertix)
As you can see if the path is already the maximal path it is untrue.
Edit :lock at the same graph but identify the vertexes $a_5,a_6$
