Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I am currently taking an introduction to graph theory course. We are using the 5th edition book by Robin J Wilson. At the end of chapter 1 there are some challenging problems I'd like to think about. But the problem is I don't exactly know what it is asking me. Here is the problem:

If $G$ is a simple graph with the edge-set $E(G)$, the vector space of G is the vector space over the field $\mathbb{Z}_2 = \{0,1\}$ of integers mod 2, whose elements are subsets of $E(G)$. The sum $E+F$ of two such subset $E$ and $F$ is the set of edges in $E$ or $F$ but not both and scaler multiplication is defined by $1\cdot E = E$ and $0\cdot E = \text{empty set}$. Show that this defines a vector spacee over $\mathbb{Z}_2$ and find a basis for it

So I've taken linear algebra, abstract algebra so I am familiar with what a vector field is. Similarly I also know what a field is and I also know simple modular arithmetic. However, I dont know how to combine everything together. If M.SE could be kind enough to go through the problem and explain what each part is doing and the meaning and possibly a solution. For example what does it mean by "vector space of G over the field.."

share|cite|improve this question
The fact that you are dealing the the edge set of a graph is irrelevant. Define the same structure on on the set of subsets of an arbitrary set $X$. My guess is, removing irrelevant details will make this easier to deal with. – Mariano Suárez-Alvarez Jan 16 '12 at 3:04
In any case, you should obviously pick up your linear algebra notes and/or textbook and review it. It is simply impossible to find a basis of a vector space if you do not know what a basis of a vector space is. On the other hand, the text you quoted is precisely the definition of the «vector space of $G$» the field $\mathbb Z_2$, so your example question is answered exactly in the text you quoted! – Mariano Suárez-Alvarez Jan 16 '12 at 3:06
Oh, I see. That was my fault, should have read more carefully. I do know what a basis is but I meant to say I don't know what it means in this context. Maybe I am just confused about it. Also about irrelevant details. I copied it right out of the text and I would prefer to leave everything because hey you just taught me that for this question, once I understand it, the edge set is irrelevant.\ – Tyler Hilton Jan 16 '12 at 3:10
@TylerHilton A basis for a vector space the same in all contexts. It is simply a set which is linearly independent and generates the vector space. In this case the vector space is the set of formal sums of edges with coefficients in $\mathbb{Z}_2$, i.e. the space of sums $c_1e_1+\cdots+c_ne_n$ where the $e_i$ are edges and the $c_i$ are in $\mathbb{Z}_2$. From this it should be easy to see that the set $\{1\cdot e:e\in E(G)\}$ is a basis for the vector space. – Alex Becker Jan 16 '12 at 3:23
Here is a good coverage of the basic graph vector spaces- vertex space, edge space, cycle space, and cut space. Note that cycle and cut spaces are subspaces of edge space.… – ml0105 Mar 13 '14 at 21:50
up vote 2 down vote accepted

This is too long for a comment, so I'll leave it up here as an answer instead. I propose you pick your linear algebra notes/textbook and with that try to do the following:

Let $X$ be a set, and let $V=\mathcal{P}(X)$ be the set of all subsets of $X$.

Define an operation $+:V\times V\to V$ as follows: if $A$, $B\in V$, so that $A$ and $B$ are subsets of $X$, then we define $A+B$ to be $A\cup B-A\cap B$.

Now show that this operation $+$ has all the properties required of the addition of a vector space—your linear algebra notes surely list them, so I won't repeat them here.

Next, we are going to consider the field $F=\mathbb Z_2$ with two elements and define a scaar multiplication $\cdot:F\times V\to V$ as follows.

For all $A\in V$ we define $0\cdot A=\emptyset$ and $1\cdot A=A$. This is enough, because $F$ has exactly two elements, namely $0$ and $1$.

Now check that this scalar multiplication $\cdot$ has all the required properties of the scalar multiplication of a vector space over the field $F$, and that $+$ and $\cdot$ are related in the way they should in order for $V$ to become a vector space with them as operations.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.