The premises tell you that $P$ is reflexive and transitive, as well as total; this means that it is a total pre-order on the domain. The conclusion is that the pre-order has a smallest element.
How would you go about doing it by induction? Well, suppose you know the result holds in any domain with fewer than $k$ elements, and your domain has $k$ elements. Pick $x_0\in D$ ($D$ the domain), and let D'=D\setminus\{x_0\}, and let P'=P\cap D'\times D'. If you can prove that P' satisfies the premises of the formula relative to D' (given that $P$ satisfies them relative to $D$), then you'll be able to conclude that there is a y\in D' such that (y,x)\in P' for every x\in D'. Now, how can $y$ fail to be an element with the right property if you now consider it in $D$? And if that happens, can you find an element that will work?
As to a counterexample, given my first paragraph, does something suggest itself?
Okay, you are asking for some more help on getting the induction going.
Let $n$ be the number of elements in the model $D$. We want to prove the formula holds for $D$. We do so by induction on $n$.
The base case is $n=1$. To establish the proposition, we are allowed to assume the premise holds: that for all $x\in D$ we have $P(x,x)$, that for all $x$, $y$, and $z$ in $D$, if $P(x,y)$ and $P(y,z)$ both hold, then $P(x,z)$ holds; and that for all $x$ and $y$ in $D$, either $P(x,y)$ holds or $P(y,x)$ holds. We want to show that there exists a $y\in D$ such that for all $x\in D$, $P(y,x)$ holds.
Since $D = \{x_1\}$ has a single element, what can $y$ be? It must be $x_1$. So you need to show that for every $x$ in $D$, $P(x_1,x)$ holds. Surely this is easy.
Okay, so now assume that you know the proposition is true in any domain with $k$ elements, and assume that $D=\{x_1,x_2,\ldots,x_k,x_{k+1}\}$ has $k+1$ elements. We are also allowed to assume that $P(x,x)$ holds for all $x\in D$, that for all $x,y,z$ in $D$, if $P(x,y)$ and $P(y,z)$ holds, then $P(x,z)$ holds; and that for all $x$ and $y$ in $D$, either $P(x,y)$ holds or $P(y,x)$ holds. We want to show that there is a $y\in D$ such that for all $x\in D$, $P(y,x)$ holds.
Consider D'=D-\{x_{k+1}\}, and let P' be a binary relation on D' defined by $P'(x,y)\text{ in $D'$} \Leftrightarrow P(x,y) \text{in $D$.}$ Verify that P' satisfies the premise of the proposition in D': for all x\in D', P'(x,x) holds; if P'(x,y) and P'(y,z) hold, then P'(x,z) hold; and for all $x$ and $y$ in D', either P'(x,y) holds or P'(y,x) holds.
By the induction hypothesis, the formula is true in D'; so if the premise is also true in D', then the conclusion is true in D'. So there is a y_0\in D' such that for all x\in D' you have P'(y_0,x).
Now, go back to $D$; $y_0$ is in $D$, and for every $x\in D$, if x\in D' (that is, if $x\neq x_{k+1}$) then $P(y_0,x)$ holds. Now, what happens to $x_{k+1}$? Well, by our premises, either $P(y_0,x_{k+1})$ holds, or else $P(x_{k+1},y_0)$ holds because $y_0$ and $x_{k+1}$ are both in $D$. Think about what each of those two things would tell you in terms of trying to find a $y\in D$ such that $P(y,x)$ holds for all $x$ in $D$.