The words "with replacement" means that after you pull out the first tag and read the number on it, you put it back ("replace it"), mix the tags up again before you pull out the second one.
Back to the question. Your idea of breaking into cases is a sound one, and the probability is indeed $P_1 + P_2$, but your expressions for those two numbers are not correct.
Case I: The probability that the first one you draw is neither $1$ or $n$ is $\frac{n-2}{n} $. This is then multiplied by the probability that the second number you draw is one of the two adjacent numbers, which is $\frac{2}{n}$ (note that it's not $\frac{2}{n-1}$, since we put the first tag back). We therefore have
$$
P_1 = \frac{n-2}{n}\cdot \frac{2}{n}
$$
Case II: The probability that the first tag is either $1$ or $0$ is $\frac{2}{n}$. The probability that the second tag in that case is the one adjacent tag number (either $2$ or $n-1$, depending on the case) is $\frac{1}{n}$. So we have
$$
P_2 = \frac{2}{n}\cdot \frac{1}{n}
$$
So we get
$$
P_1 + P_2 = \frac{2n-4 + 2}{n^2} = \frac{2n - 2}{n^2}
$$
Alternate approach: (assumes $n \geq 3$, if $n = 2$ the probability is easily seen to be $0.5$) Pretend, for a second, that we also allowed $1$ and $n$ to "connect around", so that drawing those two in any order would also count. Then no matter what you got on the first tag, there would be $2$ possible "good" second tags. So the probability would be $\frac{2}{n}$.
Now, how much probability do we lose by disallowing the $1$-$n$-connection? Well, there are $n^2$ different combinations to draw, and there are two of those possibilities that are $1$ and $n$, in some order. Therefore, the probability that you draw a $1$ and an $n$ is $\frac{2}{n^2}$. That combination is allowed in our hypothetical scenario above, but it is disallowed in the real problem, so our $\frac{2}{n}$ result overshot the target by $\frac{2}{n^2}$. Therefore the probability of drawing two adjacent tags is
$$
\frac{2}{n} - \frac{2}{n^2} = \frac{2n -2}{n^2}
$$
which is the same result.
Best Answer
Edit: Usually, these sorts of probabilities are always defined in terms of natural density. So when I say below that "the probability that $x$ is divisible by $p$ is $1/p$", this means that, if we pick a random $x$ in $\{1,\dots,N\}$, and ask about the probability that $x$ is divisible by $p$, and then let $N\to\infty$, we arrive at the intuitive fact that the probability is $1/p$.
Multiples of $p$ occur every $p$ integers, so the probability that $p$ divides $x$ is $1/p$. For distinct primes, the events are independent, so you have probability $$\frac1{p_1}\cdot\frac1{p_2}=\frac1{p_1p_2}.$$