Can a knight make every possible move on an 8x8 chess board exactly once?

[JasonJo]

a professor posed the following question in class:
Is it possible for a knight to move around an 8x8 chess board so that it makes every possible move exactly once? (consider a move between two sqaures connected by a knight to be completed when the move is made in either direction)

so i outlined an 8x8 grid. and it seems like there will be 2 vertices of odd degree and i "think" the graph is a connected graph following Euler's formula of r= e - v + 2, but obviously i can't prove or derive any of this. can anyone recommend a good approach to this problem? i don't believe there is an Euler cycle, but there is an Euler path?
*Note: this problem is posed before we ever started Hamiltonian circuits

and a general homework problem that i am having a lot of trouble proving (much like everything else in graph theory)

1) G is a planar graph that is not necessarily connected, as required in Euler's forumula. Recall that a component H is a connected subgraph of G with the property that there is no path between any vertex in H and any vertex of G not in H.
(a) find the appropriate modification of Euler's formula for a planar graph with c components
(b) show that the corollary is valid for unconnected plana graphs (e is less than or equal to (3v-6), but in terms of the new modified Euler's formula)

*this was an odd numbered problem and i looked in the back of the book, the answer was:
(a) r = e - v + c + 1
(b) corollary becomes e (less than or equal to) 3v - 3c - 3

I don't really understand the idea of connected graphs, especially counting the unbounded region twice or once, not too sure.

2) If G is a connected planar graph with all circuits of at least length k, show that the inequality e (less than or equal to) 3v - 6 can be strengthened to e (less than or equal to) (k/(k-2))
- for this one, i think i use the fact that k will be less than or equal to the sum of the degrees of the vertices or 2e, but after that i tried many ways to dervice the strengthened formula, and failed. anyone have any helpful hints to push me along?

sorry for not knowing how to use the symbols guys.

even though graph theory is a difficult class, not really necessary for what i want to do (actuarial), i love the class. it might mess up my gpa a little, but i want really badly to be able to do graph theory problems. i see it as one of the purest fields and one of the most difficult as well.

ok guys, thanks for the help

 

[Hurkyl]

(For the chess problem)

Do you agree that the graph is connected if and only if you can move a knight between any two squares on the chessboard?

And given the symmetry of the problem, don't you find it suspcious to have exactly two vertices of odd degree?

 

[JasonJo]

hmm, wow

ok, so due to the board's symmetry, if there 1 vertice of odd degree, there will be at least 4 verticies of odd degree, meaning no Euler cycle or Euler path possible. am i heading in the right direction?

hurkyl, can you expand on the if and only if statement and the graph being connected? i am very interested in that statement, i just don't quite grasp it yet

excellent hints though

*i solved the other two problems, and i thanks to you i might have the chessboard problem

 

[Hurkyl]

Just rephrase all your graph theoretical concepts in terms of chess.