edge if an edge is directedits first endpoint is its origin and the other is the destination of the edge two vertices and are said to be adjacent if there is an edge whose end vertices are and an edge is said to be incident on vertex if the vertex is one of the edge' endpoints the outgoing edges of vertex are the directed edges whose origin is that vertex the incoming edges of vertex are the directed edges whose destination is that vertex the degree of vertex vdenoted deg( )is the number of incident edges of the in-degree and out-degree of vertex are the number of the incoming and outgoing edges of vand are denoted indeg(vand outdeg( )respectively example we can study air transportation by constructing graph gcalled flight networkwhose vertices are associated with airportsand whose edges are associated with flights (see figure in graph gthe edges are directed because given flight has specific travel direction (from the origin airport to the destination airportthe endpoints of an edge in correspond respectively to the origin and destination for the flight corresponding to two airports are adjacent in if there is flight that flies between themand an edge is incident upon vertex in if the flight for flies to or from the airport for the outgoing edges of vertex correspond to the outbound flights from ' airportand the incoming edges correspond to the inbound flights to ' airport finallythe in-degree of vertex vofg corresponds to the number of inbound flights to ' airportand the out-degree of vertex in corresponds to the number of outbound flights the definition of graph refers to the group of edges as collectionnot setthus allowing for two undirected edges to have the same end verticesand for two directed edges to have the same origin and the same destination such edges are called parallel edges or multiple edges parallel edges can be in flight network (example )in which case multiple edges between the same pair of vertices could indicate different flights operating on the same route at different times of the day another special type of edge is one that connects vertex to itself namelywe say that an edge (undirected or directedis self-loop if its two endpoints coincide self-loop may occur in graph associated with city map (example )where it would correspond to "circle( curving street that returns to its starting pointwith few exceptionsgraphs do not have parallel edges or self-loops such graphs are said to be simple thuswe can usually say that the edges of simple graph are set of vertex pairs (and not just collectionthroughout this we assume that graph is simple unless otherwise specified figure example of directed graph representing flight network the endpoints of edge ua are lax and ordhencelax and ord are adjacent the in-degree of dfw is and the out-degree of dfw is