A case where the solution to Expenditure Minimisation Problem is not a solution to Utility Maximistion Problem I am looking for a preference relation which satisfies the above property.
If the utility is continuous and locally insatiable then the Hicksian demand equals the Walrasian demand.

So you'll need to look for a utility function which violates atleast one of these.

Lets try a simple violation of non-satiation $$
u(x,y) = \left\{
        \begin{array}{ll}
            x+y &amp; \quad x+y \leq 1 \\
            1 &amp; \quad \text{ otherwise}
        \end{array}
    \right.
$$

With $p=(1,1)$ and $w=2$ Then $x(p,w)=\{(x,y): 1\leq x+y\leq 2\}$. This is becuse the consumer's problem is $$\max_{x,y} u(x,y)$$ $$\text{st }x+y\leq 2$$

$u(x(p,w))=1$ so apply the EMP to this utility $$\min x+y$$ $$\text{st } x+y\geq 1$$
This gives $h(p,1)=\{(x,y): x+y= 1\}$. Hence, $h(p,v(p,w))\neq x(p,w)$.

I think a violation of non-satiation is much easier to construct a counter example with. If we have a 'thick' indifference curve then the UMP will choose the entire curve but the EMP will choose at most the lower envelope, as why spend more to get the same utility? 

Conversely, we can use continuity to find an example of where $h(p,v)$ is not a subset of $x(p,e(p,v))$. Take $p$ and $w$ as above and 

$$
u(x,y) = \left\{
        \begin{array}{ll}
            x+y+1 &amp; \quad x+y \geq 2,\ x\geq y \\
            x+y &amp; \quad \text{ otherwise}
        \end{array}
    \right.
$$

The EMP with $v=2$ is

$$\min x+y$$
$$\text{st }u(x,y)\geq 2$$

$h(p,2)=\{(x,y): x+y=2\}$. Now look at the UMP at $p,w$

$$\max u(x,y)$$

$$x+y\leq 2$$

$x(p,w)=\{(x,y):\ x+y=2, x\geq y\}$. Hence, $x(p,e(p,v))$ is a proper subset of $h(p,v)$.

I found it alot easier to come up with a counterexample without continuity (our $u$ is locally non-satiated). Perhaps with continuity you get $h\subset x$ and local non-satiation you get the reverse? Ill leave that to you.