The Blender API is a little quirky. You have to either be in OBJECT mode or use bmesh to select or deselect vertices and edges.

Let’s start with a cube, in EDIT mode, with everything deselected.

start box

To select a vertex, one way is to change to OBJECT mode, select the vertex, and change back to EDIT mode.

#change to OBJECT mode
bpy.ops.object.mode_set(mode="OBJECT")

#deselect the 0th vertex
bpy.data.meshes['Cube'].vertices[0].select = True

#change to back to EDIT mode
bpy.ops.object.mode_set(mode="EDIT")

selected vertex

Deselect works very similarly:

bpy.ops.object.mode_set(mode="OBJECT")

#deselect the 0th vertex
bpy.data.meshes['Cube'].vertices[0].select = False

bpy.ops.object.mode_set(mode="EDIT")

And we’re back to the start.

start box

Selecting an edge uses the same principle:

bpy.ops.object.mode_set(mode="OBJECT")

#select the 0th edge
bpy.data.meshes['Cube'].edge[0].select = True

bpy.ops.object.mode_set(mode="EDIT")

selected edge

Deselecting that edge is quite a bit different. You can’t just use:

bpy.data.meshes['Cube'].edge[0].select =False

You have to deselect the vertices of an edge first, and then deselect the edge.

bpy.ops.object.mode_set(mode="OBJECT")

bpy.data.meshes['Cube'].vertices[0].select = False
bpy.data.meshes['Cube'].vertices[1].select = False
bpy.data.meshes['Cube'].edges[0].select = False

bpy.ops.object.mode_set(mode="EDIT")

Occasionally, when switching the mode to deselect doesn’t work (like if you have non-manifold edges selected), or if you want to stay in edit mode, you can use bmesh.

Let’s start with a box with once face removed and non-manifold edges selected
( bpy.ops.mesh.select_non_manifold())

non manifold edges

bpy.ops.object.mode_set(mode="EDIT")
mesh = bmesh.from_edit_mesh(bpy.context.object.data)
mesh.verts[2].select = False #the vertices are indexed differently
mesh.verts[3].select = False
mesh.edges[0].select = False

deselected edge for non manifold

Ta da! The bottom edge is deselected.

Blender 2.71