How can I define alkenes using graph theory?
Perhaps you could just represent them as simple weighted graphs? Edges of weight 1 represent single bonds, while edges of weight 2 represent double-bonds.

*Edit: For condition #3 simply pick a canonical ordering for the vertices/atoms. See 

https://en.m.wikipedia.org/wiki/Graph_canonization 

http://depth-first.com/articles/2006/08/12/inchi-canonicalization-algorithm/ 

for examples