- #1
JasonJo
- 429
- 2
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 reccomend 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
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 reccomend 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