#### Reading material

If you use the first edition of the textbook, follow the reading material
in orange. If you use the second edition,
follow the reading material in brown.
(1st)
pages 350-355 (Section 9.1 and 9.2.1)

(2nd)
pages 544-550 (Section 12.1 and 12.2.1)

#### Additional material

Proof of Proposition 9.11/Proposition 12.11: PostScript and
PDF
Implementation of a simple graph by means of an edge list:
PostScript and
PDF

In order to be able to remove an edge from the set of edges in O(1), we
implement the set of edges by means of a List implemented by means of a doubly
linked list.

List edges = new DLList();

The interface Edge is implemented by the class
public class ELEdge implements Edge
{
private Object element; // element stored in this edge
private boolean isDirected; // this edge is directed?
private Vertex origin; // origin of this edge if it is directed, otherwise one of the end vertices
private Vertex destination; // destination of this edge if it is directed, otherwise the other end vertex
private Position position // position of the List in which this edge is stored
....
}

A directed edge from vertex `origin` to vertex `destination`
with element `element` can be added to `edges` as follows.
Edge edge = new ELEdge(element, true, origin, destination, null);
Position position = edges.insertFirst(edge);
edge.setPosition(position);

The edge `edge` can now be removed from `edges` as follows.
edges.remove(edge.getPosition);

#### Question

Which of the preconditions in the implementation of a simple graph by means
of an edge list cannot be checked in O(1)?