Proof in Graph Theory I have a $2D$ undirected graph of size $n \times n$ in which each node is connected to its four neighbours (left,right,top,bottom). 
If any general property is true for any nxn graph, what will be the mathematical proof for the property to hold for $(n+1) \times (n+1)$ undirected graph? All nodes are logically equivalent i.e. have some algorithm running on them.
Is induction a good choice, if so, can someone kindly give hints if the base case is $3 \times 3$. 
Thanking you in advance. 

What you have defined is a grid graph. You may find the properties of a grid graph in following links:
http://mathworld.wolfram.com/GridGraph.html 
http://en.wikipedia.org/wiki/Lattice_graph
