On an infinite table are $n$ identical circular coins lying flat. Each coin touches exactly $k$ other coins, and any two coins are connected by a path of touching coins.
Determine all possible pairs of values of $n$ and $k$.
$n$ = 1 : $k$ = 0 (single coin can't touch any others)
$n$ = 2 : $k$ = 1 (pair of coins only touch each other)
3 <= $n$ < $\infty$ : $k$ = 2 (finite number of coins greater than 2 can only touch 2 others without making the "edge" coins touch a different number [updated from Zandar])
16 <= $n$ < $\infty$ : $k$ = 3 ($n$ must be a multiple of 4 for the diamond pattern to work, update from Michael Seifert)
$n$ = $\infty$ : $k$ = 2,3,4,6 (without "edge coins" to worry about, you can look at any subset of the grid to see what connections are available. 5 can't be done on a normal 2-d euclidian surface, that would require a dodecahedron)
for the above images, assume each group of coins is a smaller selection of the infinite mass of coins, with the exception of the $k$=2 section, that is a piece of a loop
This is all I can find, there may be more.
k=0, n=0 : an empty table. (Fig A1)
k=0, n=1 : a single coin on the table. (Fig B1)
k=1, n=0 : an empty table. (Fig A1)
k=1, n=2 : two coins touching. (Fig C1)
k=2, n=0 : an empty table. (Fig A1)
k=2, n>=3 : a 'ring' of 3 or more coins, each touching its two neighbors (For example Figs. D1 - three coins, and A2 - 5 coins, )
k=3, n=0 : an empty table (Fig A1)
k=3, n=4(m+4), m>=0 : closed loop of four or more repeated blocks of four coins (For example Fig B2 - m=0, and Fig C2 - m=1)
k=3, n=∞ : infinite double row of coins in squared arrangement (Fig A3)
k=3, n=∞ : infinite hexagonal array with every third coin in each row removed. (Fig D3)
k=4, n=∞ : infinite square array of coins (Fig B4), or infinite hexagonal array with every second coin in every second row removed. (Fig A4)
k=4, n=∞ : infinite double row of coins in hexagonal arrangement (Fig B3)
k=5, n=∞ : infinite hexagonal array with one in seven of the coins removed. (Fig C4)
k=6, n=∞ : infinite hexagonal array with no coins removed. (Fig D4)
k>=7, n=0 : empty table again for all these 'impossible' options.
Nothing scientific in my answer, just by first impression and looking for possible symmetric arrangements:
On a finite n: n=1, k=0 n=2, k=1 (two coins next to each other) n>=3, k=2 (loop chain of 3 or more coins)
Seems odd that I cannot find a valid composition where k>3 and n is finite. I definitely have to give this further thought.
For infinite n, since there would have to be a symmetric arrangement, k could have any value from 2 to 6 except 5: 2 (i.e. infinite row of single coins), 3 (i.e. two parallel rows), 4 (i.e. two parallel rows offset by half a coin in "zigzagish" form), and 6 (i.e. infinite arrangement of coins as tightly as possible).
I can't figure out an arrangement where k=5, which is quite interesting. Possibly because its impossible to have a 2 dimensional symmetrical arrangement of 5 vertices.
n = infinity, k = 6. Arranged as a hexagonal pattern.
n = infinity, k = 4. Arranged as a square pattern