Maximum number of leaves in spanning tree

graph theorytrees

We have a graph with $9n^2$ vertices and put vertices in a $3n*3n$ table. two vertices are adjacent in graph if they are adjacent in table. what is maximum number of leaves in a spanning tree of this graph.

I think the answer is $6n^2-2(n-1)$ and i have a example for this but i can't prove that there's no spanning tree with more leaves. please let me know if you have any idea how to solve this.

This is my example:

this is for $n=2$

It's easy to find the pattern for bigger n.

Best Answer

This is a construction that gives $6n^2-n$

enter image description here