Based on above graph, find the orderings satisfying
1) every vertex other than the last is adjacent to some vertex that comes later in the ordering
2)the final vertex has non-maximal degree
by second condition, it seems that vertex 6 should be the last one since it has non-maximal degree.
However, if you proceed on the left side by ordering vertices from
1,2,3,4,5 so that every vertex is adjacent to vertex that comes later in the ordering.
Since 6 has to be the last one, the next vertex that comes after 5 must be either 7,8,9,10, or 11 but those vertices are not adjacent to 5.
Did I misunderstand something?
For second question,
If a graph is connected and non-regular, is it always possible to order the vertices so that conditions (1) and (2) are satisfied?
I think this is not possible, since square has all vertices of degree 2 and every vertex has maximal degree.
Is that one counter-example?
Thanks
(1) Yes, you are misinterpreting something. The condition requires that each vertex (except for the last one, of course) appears before a vertex adjacent to it, but NOT that it appears immediately before that one. So you can extend the segment that you've already constructed as $$\ldots,7,1,2,3,4,5,6.$$ Adding $7$ there satisfies the given requirements, because $7$ is adjacent to $6$, which does appear later than $7$ in this ordering.
(2) The square is not a valid counterexample here, because the statement talks about non-regular graphs. A graph is regular if all its vertices have the same degree. Precisely for the reason that you described (that there wouldn't be a vertex with a non-maximal degree) such graphs are specifically excluded from this statement.