Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
4  
The proof depends on the property. And if all have four neighbours - is the graph rolled to a torus? –  Hagen von Eitzen Apr 8 at 10:08
    
Thank you very much for your kind response. Graph is not rolled to a torus i.e. The edge nodes have only 2 or 3 neighbours. In fact, it is a square grid graph. –  Curious Apr 9 at 6:39
    
Property is any general property. is it not possible to prove it in general, without specifying any property? –  Curious Apr 9 at 6:41

1 Answer 1

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

share|improve this answer
    
Thank you very much for the technical correction. Yes, exactly this is a square grid graph. –  Curious Apr 9 at 6:41
    
Can you please suggest any hint on how to prove or disprove the argument? –  Curious Apr 10 at 7:43
    
If you're writing a paper, you can refer to the articles. Else, you can read the papers and copy the proofs from the papers. –  cagirici Apr 10 at 19:12

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.