If you have a signal x with N samples acquired at a sampling rate Fs, then:
1) The time axis of your vector x (the time associated with each individual sample in the vector x) is:
The difference in time between two sucessive samples is 1/Fs, and the samples/elements in x range between t=0 to t=(N-1)/Fs
2) The frequency axis of your vector fft(x) (the frequencies associated with each element in the vector fft(x)) is:
f = [0:floor(N/2) -ceil(N/2)+1:-1]*Fs/N;
or you could just write f = (0:N-1)*Fs/N if you understand how frequencies above Fs/2 wrap-around the negative axis (i.e. when sampled at a sampling frequency Fs a sine with frequency -Fs/N would look just the same as a sine with frequency Fs*(N-1)/N)
The difference in frequency between two sucessive samples of fft(x) is Fs/N (this is the same as the smallest non-zero frequency that you are measuring), and the samples/elements in fft(x) range between approximately -1/(2*Fs) and 1/(2*Fs)
The two definitions that you are mentioning for tmax are just the same. In other words, min(freq) (the smallest non-zero frequency that you are measuring) is Fs/N, which is just the same as the difference between two sucessive frequencies in your frequency axis (you are naming this fs, I would probably have chosen a different name to avoid confusing this with Fs, your sampling frequency).
Also please note that, more precisely, tmax would not be equal to N/Fs but rather to (N-1)/Fs (or (1-1/N)/min(f) using your notation), but that is probably a minor point to make.
And last, regarding why your timeseries x duration (in seconds) is related to the frequency interval of your fourier transformed signal fft(x), for a fixed sampling frequency Fs, the longer that you acquire the signal x, the more densely you are able to sample the fixed -1/(2*Fs) to 1/(2*Fs) frequency interval, so it is natural that you may relate the length of your timeseries x to the density of this frequency sampling.
