same endpoints and there are no self-loopsthe maximum degree of vertex in is in this case thusby proposition < ( now suppose that is directed since no two edges can have the same origin and destinationand there are no self-loopsthe maximum in-degree of vertex in is in this case thusby proposition < ( path is sequence of alternating vertices and edges that starts at vertex and ends at vertex such that each edge is incident to its predecessor and successor vertex cycle is path with at least one edge that has its start and end vertices the same we say that path is simple if each vertex in the path is distinctand we say that cycle is simple if each vertex in the cycle is distinctexcept for the first and last one directed path is path such that all edges are directed and are traversed along their direction directed cycle is similarly defined for examplein figure (bosnw jfkaa dfwis in directed simple pathand (laxua ordua dfwaa laxis directed simple cycle if path or cycle is simple graphwe may omit the edges in or cas these are well definedin which case is list of adjacent vertices and is cycle of adjacent vertices example given graph representing city map (see example )we can model couple driving to dinner at recommended restaurant as traversing path though if they know the wayand don' accidentally go through the same intersection twicethen they traverse simple path in likewisewe can model the entire trip the couple takesfrom their home to the restaurant and backas cycle if they go home from the restaurant in completely different way than how they wentnot even going through the same intersection twicethen their entire round trip is simple cycle finallyif they travel along one-way streets for their entire tripwe can model their night out as directed cycle subgraph of graph is graph whose vertices and edges are subsets of the vertices and edges of grespectively for examplein the flight network of figure vertices bosjfkand miaand edges aa and dl form subgraph spanning subgraph of is subgraph of that contains all the vertices of the graph graph is connected iffor any two verticesthere is path between them if graph is not connectedits maximal connected subgraphs are called the connected components of forest is graph without cycles tree is connected forestthat isa connected graph without cycles note that this definition of tree is somewhat different from the one given in namelyin the context of graphsa tree has no root whenever there is ambiguitythe trees of should be referred to as rooted treeswhile the trees of this should be referred to as free trees the connected components of forest are (freetrees spanning tree of graph is spanning subgraph that is (freetree example perhaps the most talked about graph today is the internetwhich can be viewed as graph whose vertices are computers and whose (undirectededges