If you are going to check edge existence only few times, why care about the time complexity? If you are going to check it regularly, why don't use some better data structure (adjacency matrix, as already mentioned).
But even with an incidence matrix, you can probably do better then O(E) and still call it an incidence matrix :).
Given an incidence matrix with row for each vertex and column for each edge, most of the elements of the matrix will be zeroes (there will be at most V nonzero elements on each row). That's called sparse matrix and it can be stored in the memory in some space efficient way, which also allows "skipping" long sequences of zeroes in constant time.
For example with simple list of lists representation, you have a list of pairs (columnindex, value) ordered by columnindex for each row, one pair for each nonzero element. In our case, just check rows u and v, whether they have an item with same columnindex. As they are both ordered and both have less then V items, it can be done in O(V).
Of course, it's a trade-off. Some other operations are less efficient if matrix is stored this way.
If we remove one of the additional vertices from $G'$, the resulting graph contains an Eulerian walk $W_1$ since there are now two vertices of odd degree. Removing the next additional vertex splits $W_1$ into two walks, let's call them $W_1, W_2$. Removing the next vertex splits one of the walks $W_1, W_2$ into two walks again resulting in walks $W_1, W_2, W_3$. Repeat until all additional vertices have been removed, count the walks produced.
Since an Eulerian walk visits every edge exactly once, splitting it into several parts results in edge disjoint walks and because we only removed the additional edges and vertices, the resulting walks cover $G$.
Best Answer
You can solve the maximum independent set problem via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether node $i\in N$ is selected. The problem is to maximize $\sum_{i\in N} x_i$ subject to $$x_i + x_j \le 1 \quad \text{for all $(i,j)\in E$}.$$ These constraints enforce $(i,j)\in E \implies \lnot(x_i \land x_j)$. That is, if $(i,j)$ is an edge you cannot select both nodes $i$ and $j$.
In practice, integer linear programming is much more efficient than brute force.