In the game of chess, a knight is a piece that can only move in \"L\" shapes aro

Question

In the game of chess, a knight is a piece that can only move in "L" shapes around the board. More precisely, it can move two squares either vertically or horizontally and then one square in a perpendicular direction. Depending on where the knight is situated on an 8 times 8 chessboard, he has a minimal mobility of 2 moves when he's in a corner and a maximal mobility of 8 moves when he's at least two squares away from any edge of the board (as shown in the figure below). Let G be the graph that shows all the moves a knight can make on a chessboard. This graph - which has beautiful symmetry - is called the Knight's Graph. G has then 64 vertices, where each vertex corresponds to a square of the chessboard. Moreover, two vertices of G are joined by an edge whenever a knight can go from one of the corresponding squares to the other in one move. Is G a ''pen-traceable" graph? In other words, can you trace over every edge of G exactly once and never lift your pen from the graph? Justify your answer fully.

Explanation / Answer

In G a "Pen-traceable" graph. can be done with Euler's networks.

Before starting this answer we will discuss about the Euler's and then will justify the answer.

Gratesh mathematician of the 18th century.wrote close to 800 pages of mathematical discoveries every year for 60 years . Euler appears ont he swiss 10 franc note.He made numerous contributions to mathematical physics including the theory of fluid flow(used in studying how to make airplanes fly) and the theory of rotations of rigid bodies.

He was blind for the last 17 years of his life. Even though he had this disability he continued writing by dictation. Euler made many discoveries. one discovery he made is called Networks. A network is traceable if you can trace each edge without lifiing your pencil. this Example is called a "Euler Circuit" because it starts at point A and returns to the same point A. without repating any edges.

We're going to work on tracing graphs. These aren't x-y graphs from algebra, these are just collections of vertices and edges. The same rules hold for these edges as for the ones we used for Euler Characteristic calculations:

Vertices have to go at crossings and at endpoints. You are also allowed to put in extra vertices to split an edge into two edges.

Edges go between veritices. They are squiggly and sometimes zig-zaggy lines. Edges always start and end at vertices (though sometimes they can start and end at the same vertex

A traceable graph is one where you can trace the whole thing, without ever going over the same line twice, and without lifting your pen/pencil.

This path is an Euler circuit because it starts and ends at the same vertex.

This path is an Euler path, but not an Euler circuit because it doesn't start and end in the same place

Since based on the above contains we can prove the Pen-traceble.

You can also you this proof :

Euler Graphs

A closed walk in a graph G containing all the edges of G is called an Euler line in G. A graph containing an Euler line is called an Euler graph.

We know that a walk is always connected. Since the Euler line (which is a walk) contains all the edges of the graph, an Euler graph is connected except for any isolated vertices the graph may contain. As isolated vertices do not contribute anything to the understanding of an Euler graph, it is assumed now onwards that Euler graphs do not have any isolated vertices and are thus connected.

Example Consider the graph shown in Figure below Clearly, v1 e1 v2 e2 v3 e3 v4 e4 v5 e5 v3 v6 e7 v1 in (a) is an Euler line, whereas the graph shown in (b) is non-Eulerian.

Theorem (Euler): A connected graph G is an Euler graph if and only if all vertices of G are of even degree.

Proof

Necessity Let G(V, E) be an Euler graph. Thus G contains an Euler line Z, which is a closed walk. Let this walk start and end at the vertex u V . Since each visit of Z to an intermediate vertex v of Z contributes two to the degree of v and since Z traverses each edge exactly once, d(v) is even for every such vertex. Each intermediate visit to u contributes two to the degree of u, and also the initial and final edges of Z contribute one each to the degree of u. So the degree d(u) of u is also even.

Sufficiency Let G be a connected graph and let degree of each vertex of G be even. Assume G is not Eulerian and let G contain least number of edges. Since 2, G has a cycle. Let Z be a closed walk in G of maximum length. Clearly, GE(Z) is an even degree graph. Let C1 be one of the components of G E(Z). As C1 has less number of edges than G, it is Eulerian and has a vertex v in common with Z. Let Z be an Euler line in C1. Then Z Z is closed in G, starting and ending at v. Since it is longer than Z, the choice of Z is contradicted. Hence G is Eulerian.

Second proof for sufficiency Assume that all vertices of G are of even degree. We con- struct a walk starting at an arbitrary vertex v and going through the edges of G such that no edge of G is traced more than once. The tracing is continued as far as possible. Since every vertex is of even degree, we exit from the vertex we enter and the tracing clearly cannot stop at any vertex but v. As v is also of even degree, we reach v when the tracing comes to an end. If this closed walk Z we just traced includes all the edges of G, then G is an Euler graph. If not, we remove from G all the edges in Z and obtain a subgraph Z of G formed by the remaining edges. Since both G and Z have all their vertices of even degree, the degrees of the vertices of Z are also even. Also, Z touches Z at least at one vertex say u, because G is connected. Starting from u, we again construct a new walk in Z. As all the vertices of Z are of even degree, therefore this walk in Z terminates at vertex u. This walk in Zcombined with Z forms a new walk, which starts and ends at the vertex v and has more edges than Z. This process is repeated till we obtain a closed walk that traces all the edges of G.

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.