Take the 2-minute tour ×

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 (although I seem to have forgotten what basis 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|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. dreamincode.net/forums/topic/… –  ml0105 Mar 13 '14 at 21:50

1 Answer 1

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|improve this answer

Your Answer


