Hello Vital Sine! Today we're going to talk about
king's graphs. An n-by-k kings graph is a type of graph whose vertices represent squares on an n-
by-k chess board, and whose edges represent all possible legal moves of a king on a chessboard
every connection between two vertices in a king's graph represents a legal move of a king between
the squares represented by those two vertices. For those unfamiliar with chess, a king can move one
square in any direction from its current square. Moving on, we are familiar with the 8 x 8 chessboard,
and the legal moves of a king on this chessboard would be captured by an eight by eight king's
graph. However, king's graphs can have different dimensions as well, such as three by five, six by
seven, any pair of positive whole numbers really. In graph theory terms, an n by k king's
graph is defined as the strong product of a path graph with n vertices with a path
graph with k vertices. For example, a three by four king's graph is the strong product of a three
vertex path graph with a four vertex path graph. I recommend you watch my video on
strong products of graphs if you haven't already, as strong products
will be very important in this video. Using our new definition, the king's
graph corresponding to our typical 8 by 8, 64 square chessboard is the strong product
of two path graphs with eight vertices each. Now let's look at why a strong product of two path
graphs produces a graph that captures the legal moves of a king on a chessboard. Picture a chess
board where we label the rows with numbers one through eight, and we label the columns with
letters a through h. If our king is stationed at b1, then it can move to squares in the same row
but in an adjacent column (that is, c1 and a1), or it can move the squares in the
same column but in an adjacent row (that is, b2), and it can move to squares in both
an adjacent column and an adjacent row (that is, a2 and c2). That means that for a king's graph,
where each square is represented by a vertex, the vertex representing square b1 should have
connections to a1, c1, b2, a2, and c2. The key concept here is that a king can move side to side one
step, up and down one step, and diagonal one step. If a king's graph is to capture the structure
of the legal moves of a king on a chess board, any two vertices defined by ordered pairs (x1, y1)
and (x2, y2), where x's are their column letters and y's are their row numbers, will connect if they
have the same column letter and consecutive row numbers (that is, x1 equals x2 and y1 and y2 are
consecutive numbers), or if they have the same row number and consecutive letters (that is, y1
equals y2 and x1 and x2 are consecutive letters), or finally they will connect if the two vertices
have consecutive row numbers and consecutive column letters (that is, x1 and x2 are consecutive
letters and y1 and y2 are consecutive numbers). Doesn't this definition of ordered pairs remind
you of the strong product of two graphs where each vertex in the strong product represents an
ordered pair of vertices from the factor graphs? And does our idea of connecting vertices that
are in adjacent columns but the same row, or in adjacent rows but the same column, or an adjacent
rows and adjacent columns, remind you of the adjacency conditions of strong products of graphs?
If these concepts feel similar it's because they are, as we'll cover right now. Think of the strong
product of two path graphs on eight vertices: one labeled with letters a through h and the
other labeled with numbers one through eight. As we learned in previous videos, the strong
product of these two graphs will have 64 vertices, each corresponding to an ordered
pair vertices from the path graphs. According to the first adjacency rule for strong
products (highlighted in yellow) two vertices in the strong product are connected if the first entries
in their ordered pairs (in this case their letters) are the same vertex in the first graph, and if
their second entries in their ordered pairs (in this case their numbers) are adjacent vertices in
the second graph (in this case consecutive numbers or vertices in the second graph) are adjacent,
which means that all strong product vertices with the same letter and consecutive numbers will
connect to each other. This means that each vertex in a column will connect to the vertices one step
above and one step below it in that column. This is precisely the property we're looking for in
a king's graph, where vertices in the same column but adjacent rows should connect, corresponding to
an up and down movement of a king on a chessboard. According to the second adjacency rule for strong
products of graphs, two vertices in the strong product are connected if their second entries
in their ordered pairs (in this case their numbers) are the same vertex in the second graph and their
first entries in their ordered pairs (in this case their letters) are adjacent vertices in the first
graph. In this case, consecutive letters or vertices in the first graph are adjacent, which means that
all strong product vertices with the same number and consecutive letters will connect to each
other. This means that each vertex in a row will connect to the vertices one step to the
right and one step to the left in that row. This is exactly the property of a king's
legal moves where a king can travel to any square in an adjacent column but in the same
row. Finally, according to the third adjacency rule, two vertices in the strong product are
connected if their first entries in their ordered pairs are adjacent vertices in the
first graph, and their second entries in their ordered pairs (in this case their numbers)
are adjacent vertices in the second graph. In our case consecutive letters or vertices in the
first graph are adjacent, and consecutive numbers or vertices in the second graph are adjacent,
which means that all strong product vertices with consecutive letters and consecutive numbers will
connect to each other. This is exactly the property that a king on a chessboard can move to diagonally
adjacent squares on that chess board. That's it! That's the strong product of two path graphs with
eight vertices each, giving us the eight by eight kings graph. It's pretty neat that the adjacency
rules of the strong product and the adjacencies within path graphs allow us to capture the
properties of a king's legal moves on a chessboard. To finish the video, let's take a look
at some properties of king's graphs. What's the longest shortest path between any two
vertices in an n by k king's graph? The answer is the maximum of (n, k). Why is this? Well
picture any vertex in an n by k kings graph, in this case an 8 by 8 kings graph. We can
represent each vertex with a set of coordinates where the x coordinate is its column number
and the y coordinate is its row number. If we have two vertices and
examine their coordinates, we see that their horizontal distance
H is the difference of their x coordinates and their vertical distance V
is the difference of their y coordinates. The quickest way to travel between
these vertices is to take a diagonal in the direction that decreases both their
horizontal and vertical distance at the same time. If we do this for the minimum of (H, V) steps we get
to a position that has either zero horizontal or zero vertical distance to our destination
vertex, and max(H, V) - min(H, V) horizontal or vertical distance
remaining to our destination vertex. Think of it as eating into our bigger distance,
be it vertical or horizontal, using our smaller distance. Taking these steps we get that the
distance between two vertices in a king's graph with horizontal distance between them
H and vertical distance between them V is min (H, V) + max(H, V) - min (H, V). That would just be the maximum of the horizontal and vertical distances.
Note that the maximum possible vertical or horizontal distance between vertices is either
n or k, whichever is larger, so the maximum of (n, k) is the longest shortest path between any two
vertices in an n by k kings graph. What about the size, or number of edges, of a king's graph? Feel
free to pause the video and work this out yourself. If we have an n by k king's graph then we have
(n - 1) *(k - 1) squares in our graph. Each of these squares
corresponds to two diagonal edges. That gives us 2 times (n - 1) times (k - 1)
diagonal edges. Now we also have the horizontal and vertical edges to count. Notice that if you discard
the diagonal edges what we are left with is a grid. Each column of vertices contains (n - 1) vertical edges and each row of vertices contains (k - 1) horizontal edges. How many
columns are there? k. How many rows are there? n. So that would give us n *(k - 1) + k * (n - 1)
horizontal and vertical edges. All together now, we have this expression
for the total number of edges in our graph. That's the size of a king's graph. We can
simplify this to 4nk - 3(n + k) + 2 Finally, what is the
chromatic number of an n by k kings graph? It is 4, as long as the minimum of n and k is
greater than one. This is because as long as the minimum of n and k is greater than one, there will
always be a 4-clique, or a set of four mutually adjacent vertices in our graph, meaning that the
chromatic number is at least four. We can color any such king's graph in exactly four colors like this:
Notice that we switched color schemes every row, and within each row we alternated between two
colors. That's it for this video! In my next video, we'll cover Sperner's lemma, and in the future
we'll come back to some chess related graphs and other graph operations. Thanks for watching! Please
subscribe, like, share, and comment. Have a great day!