Dimension of vector space formed by taking subsets of graph $G = (V, E)$ We construct a vector space as follows:
Take a graph $G = (V, E)$.  Then our space will be a subspace of $\mathbb{F}_2^{|E|}$. $G$ is connected.
For every $U \subseteq V$, let the boundary of $U$ be all the edges such that one end is in $U$ and the other isn't. Put an arbitrary ordering on $E$ so that any element $x \in \mathbb{F}_2^{|E|}$ indicates a potential boundary- namely $b(U) \in \mathbb{F}_2^{|E|}$  such that $(b(U))_i = 1 \iff  $ the $i$th edge is in the boundary of $U$.
Now notice that given two $U, U' \subseteq V$: $b(U) + b(U') = b(U \Delta U')$ (this is easily seen).
In that case we may now define a linear subspace $\{b(U): U \subseteq V\} \subseteq \mathbb{F}_2^{|E|}$.
Now my question is: what is the dimension of this subspace?
It is at most $|V|$ since the sets $\{v\}$ for $v \in V$ span the space. Meaning, for any $U\subseteq V$, it is easy to see that $b(U) = \sum_{v\in U}b(\{v\})$. But this is not linearly independent since $\sum_{v\in V}b(\{v\}) = b(V) = 0$.
I want to guess that it is $|V| - 1$ but I'm not sure- I'm unable to produce a basis, only linearly dependent spanning sets.
 A: The following is a general treatment, taken from Tutte's Graph Theory. As Daniel has alluded to above, your specific construction is well-known as the cut space, and can be specifically studied in that form.

Let $R$ be a ring. Your vector subspace $V$ is an example of a chain-group on the orientation $\Omega$ of the edge set of $G$, which is an $R$-submodule of $R^{\Omega}$.
This is a famous chain-group, known as the coboundary chain-group of a graph. To construct it, we will let $\mu_{\Omega,v}(e)$ be the indicator for orientation for each $v \in V(G)$ and $e \in \Omega$:
$$\mu_{\Omega,v}(e) = \begin{cases} 1 &\text{ if $v$ is the head of $e$} \\ -1 &\text{ if $v$ is the tail of $e$} \\ 0 &\text{ if $e$ is a loop or $v$ is not incident to $e$}\end{cases}$$
Let $f \in R^{V(G)}$. Then the coboundary of $f$, written $\delta f$, is the element of $R^{\Omega}$ defined:
$$\delta f(e) = \sum_{v \in V(G)} \mu_{\Omega,v}(e)f(e)$$
Observe that if we let $R = \mathbb{Z}/2\mathbb{Z}$, and $\Omega$ be any orientation of $G$, then the set of coboundaries of $R^{|V(G)|}$ (which we will write generally as $B^1(\Omega,R)$) is precisely your vector subspace $V$.
If $f_v$ is the indicator function for $v \in V(G)$, then we call $\delta f_v$ the coboundary of $v$, and write it $\delta v$.
Here is the relevant theorem:

Theorem: (Tutte, Theorem VIII.46)
Let $C$ be the set of components of $G$, and $x_c$ a vertex in each $c \in C$. If $X = V(G) \setminus \{x_c : c \in C\}$, then the set:
$$\{\delta x : x \in X\}$$
spans $B^1(\Omega,R)$, and is linearly independent.

Let $k$ be the number of components of $G$.
As $B^1(\Omega, \mathbb{Z}/2\mathbb{Z})$ (your $V$) is a vector space, it follows that its dimension is $|V(G)| - k$. If $G$ is connected as in your case, you are correct that its dimension is $n - 1$.
