As far as I know, there is no "minimum sample size" when it comes to Tukey test. The suitability to perform a multiple comparison procedure is mostly arbitrary and highly dependant on the type of data. However, I must say that in my opinion 4 samples (and therefore 4 cases/group) is too low in any circumstances. Maybe you can collect some more data?
The answer is two. This is the smallest sample size that will allow calculation of a standard deviation. You can put numbers into the statistical software and you will get numbers out. Fewer replicates will result in some form of error.
Sample size is important for all statistical tests. There are no exceptions. A sample size of two is usually unpublishable. A sample size of 4 in each treatment may be publishable in some cases, though possibly only as a pilot study or preliminary data. In many scientific fields a sample size of 10 to 20 is considered good, but in others you will need a few thousand. Survey methods often have larger sample sizes. Things like clinical trials also have larger sample sizes.
You could think of this as risk management. If you love risk, then keep sample sizes small. It increases the chance that a similar study will come to contrary conclusions. It increases the risk that you will not find any significant result. It increases the risk that your analysis will be inappropriate or at least suboptimal. If results can cause financial or physical harm, there may be a legal/social/monetary cost if you come to the wrong conclusions. It increases the risk that your manuscript will be rejected (due to small sample size), especially if your study with a small sample size draws conclusions contrary to current paradigms. Of course there are some benefits to small sample size that include lower cost and shorter time to get the research done.