Diameter of graph-usual chessboard

[evinda]

Hello! ;)

I am given this exercise:
A graph has as vertices the $64$ squares of an usual chessboard and two squares are connected with an edge if and only if they have a common side.Which is the diameter of the graph?

I thought that the diameter is equal to $64$,but I am not sure..Could you tell me if it is right?? (Blush)(Blush)

 

[I like Serena]

Hello! ;)

I am given this exercise:
A graph has as vertices the $64$ squares of an usual chessboard and two squares are connected with an edge if and only if they have a common side.Which is the diameter of the graph?

I thought that the diameter is equal to $64$,but I am not sure..Could you tell me if it is right?? (Blush)(Blush)

Hi! :)

I don't think so... (Worried)
What is the definition of the diameter?

 

[evinda]

Hi! :)

I don't think so... (Worried)
What is the definition of the diameter?

Diameter of a graph $G$ is defined to be tha largest distance between two vertices of $G$:
$$diam G= \max_{u,v \in V} d(u,v)$$
$d(u,v)$: distance of $u$ and $v$

How can I find it then?? (Thinking)

 

[I like Serena]

Diameter of a graph $G$ is defined to be tha largest distance between two vertices of $G$:
$$diam G= \max_{u,v \in V} d(u,v)$$
$d(u,v)$: distance of $u$ and $v$

How can I find it then?? (Thinking)

Good! :)

I like to say that the diameter is the longest shortest path.

Well, if you think it is 64, can you find a (shortest) path between 2 nodes that contains 64 edges?
What is the longest shortest path that you can find? (Wondering)

 

[evinda]

Good! :)

I like to say that the diameter is the longest shortest path.

Well, if you think it is 64, can you find a (shortest) path between 2 nodes that contains 64 edges?
What is the longest shortest path that you can find? (Wondering)

I don't really know (Worried) Could you give me a hint?? (Blush)

 

[I like Serena]

I don't really know (Worried) Could you give me a hint?? (Blush)

Well... we can only go from one square to another if those squares are next to each other.
So if we start from 1 end of the board and step to the other side, we're making 8 steps. We can't do it any faster.
That means that the diameter is at least 8.

If we start from one square and take 64 steps to get to some other square, then I think we can also find a shorter path (the distance of 2 squares is the length of the shortest path).
That means that the diameter is less than 64.

Can you find 2 squares for which it will have to take more than 8 steps to cross from the one to the other? (Wondering)