Let $S_\omega$ denote the collection of bijections $f:\omega\to\omega$. We say that $f \in S_\omega$ has a fixed point if there is $x\in \omega$ with $f(x) = x$.
It is a short exercise to show that if $f,g\in S_\omega$ then $g\circ f$ has a fixed point if and only if $f\circ g$ has a fixed point.
Let $$E = \big\{\{f,g\}: f\neq g \in S_\omega \text{ and } f\circ g \text{ has a fixed point}\big\}.$$
Question. If $G$ is a finite graph, is $G$ isomorphic to an induced subgraph of $(S_\omega, E)$?
Yes, and in addition we can choose the elements to be fixed-point-free order 2 elements in a finite symmetric group. For order 2 elements, the incidence relation means $f(x)\neq g(x)$ for every $x$.
Let $V$ be your graph (sorry $G$ sounds too group-wise to me): I view it as a graph structure on $\{1,\dots,n\}$.
Start with the discrete graph: consider the $n$ basis elements $g_1,\dots,g_n$ in the group $C_2^{n}$ since the action is free, they satisfy the condition.
For the general case, we start with the same, but letting $C_2^n$ acting freely on the disjoint union of $n(n-1)/2$ copies $X_{i,j}$ of $C_2^n$ (indexed by pairs $(i,j)$ for $1\le i<j\le n$. Let $g_1,\dots,g_n$ be the corresponding initial elements in the symmetric group over $\frac{n(n-1)}{2}2^n$ elements.
Then, for each edge, say between $i$ and $j$ for $i<j$, choose $x$ in the $(i,j)$-copy $X_{i,j}$. Then the $\langle g_i,g_j\rangle$-orbit of $x$ is of cardinal 4: then define $h_i$ as $g_i$ modified on this orbit to coincide with $g_j$ (and $h_i=g_i$ outside $X_{i,j}$ too). Hence, for $k\notin\{i,j\}$, it still holds that $h_k(y)\neq h_i(y)$ for all $y\in X_{i,j}$.
The resulting elements $h_1,\dots,h_n$ satisfy the requirements.
Note 1: said otherwise: I solved the problem for the graph consisting of a single edge, and then it works by taking a disjoint union over all edges.
Note 2: it produced an action on $2^n\frac{n(n-1)}{2}$ elements (that is a map into a group of size $(2^n\frac{n(n-1)}{2})!$) but this huge size is certainly far from optimal. If for the graph with $n$ vertices and a single edge one can do $u_n$ then one can get $u_n\frac{n(n-1)}{2}$, and $u_n$ can be taken much smaller. Already this maps into a group of size $\ge (n^2/2)!$ and is probably not very optimal either.
Edit: here's an alternative construction.
Given the incidence graph on $\{1,\dots,n\}$, consider the Coxeter group: $$W=\langle x_1\dots x_i\mid x_i^2=1, \text{for }i<j\;(x_ix_j)^2=1 \text{ if }i\,—\,j,\;(x_ix_j)^3=1\text{ otherwise}\rangle.$$
For classical theory, $x_i$ has order 2 in $W$ and $(x_ix_j)$ has order $2$ or $3$ according to the prescribed order. Let $W$ first act on itself on the left, and then let $W$ act on the set of (unordered) pairs in $W$. Then $x_ix_j$ acting on $W$ with only 2-cycles or with only 3-cycles: in the first case it fixes many pairs, while in the second case it fixes no pair. Hence the action satisfies the requirements.
Moreover using that $W$ is residually finite, one can pass to a quotient $W/N$ in which the image of the generators are distinct, and then pass the action on pairs, which has the same properties. This ought to be quantitative (i.e., one such quotient should exist with some reasonably not too large index) but I haven't checked.
