Draw a 5 × 5 grid graph. How many edges does the n × n grid graph have?

just confuse with this problem. What is n × n grid graph and how many edges it has?

• What have you tried? What research have you done? Let me help with Google toss - grid graph. Besides easily found definition it is pure basic math, so this is not the best possible question here. – Evil Aug 24 '16 at 15:01
• @Evil All other faults of the question aside, I think graph theory is firmly ontopic here. – Raphael Aug 26 '16 at 0:24
• You should only ask one question per post. Chances are that once you know what a grid graph is you can solve the second question for yourself. – Raphael Aug 26 '16 at 0:25
• @Raphael sure, the graph theory certainly is, but counting edges on grid - is it really? – Evil Aug 26 '16 at 0:29
• @Evil It is a combinatorics question but would be part of analysing many a graph algorithm's performance on grid graphs. – Raphael Aug 26 '16 at 8:08

a quick google search shows a grid graph to be http://mathworld.wolfram.com/GridGraph.html

so given that a 5 x 5 grid graph would have 25 nodes we can calculate the number of edges using this formula

A grid graph G_(m,n) has mn nodes and (m-1)n+(n-1)m=2mn-m-n edges

(5-1)5+(5-1)5=2(5)(5)-5-5 = 50 - 10 = 40

the formula itself generalized to nxn is the answer for the second portion

(n-1)n+(n-1)n=2nn-n-n = 2n^2-2n

• thanks this really helpful.but if this equation is solve further then it give zero answer is this correct or not? – alma Aug 24 '16 at 15:10
• order of operations, you have to resolve the exponent before the subtraction. – James Aug 24 '16 at 15:12
• additionally, sanity check your assumptions, there is no way that the general formula can equal zero if n is non 0 -> let nxn = 0, let n = 5, 5x5 grid = 40, 0 != 40 – James Aug 24 '16 at 15:21
• ok thanks alot . My problem is solved ! – alma Aug 24 '16 at 15:24
• Where does this formula come from? Why is it correct? – Raphael Aug 26 '16 at 0:25

The $a \times b$ grid graph has the vertex set $[a] \times [b]$, and edges of two types: horizontal edges $(i,j),(i+1,j)$ (of which there are $(a-1)b$) and vertical edges $(i,j),(i,j+1)$ (of which there are $a(b-1)$), for a total of $ab$ vertices and $(a-1)b+a(b-1)=2ab-a-b$ edges.

Start by counting the left edges and top edges, then add in the missing right and bottom edges.

For a $m \times n$ grid graph, there are $m \times n-1$ left edges (a left edge for each column at each row). Similarly, there are $m-1 \times n$ top edges. At this point, we are still missing the bottom edges for the last row, and the right edges for the last column. There are $n-1$ remaining right edges, and $m-1$ remaining bottom edges. Hence, the number of edges of an $m \times n$ grid graph is $|E_{m \times n \text{ grid}}| = m(n-1) + (m-1)n = mn-m+mn-n = 2mn-m-n$.