properties if graphghas edges then svg deg( if di-graphghas edges then svg indeg(vm svg outdeg(vif simple graphghas edges and verticesif is also directed then < ( - if is also undirected then < ( - )/ so simple graph with vertices has ( edges at most more terminology path is sequence of alternating vetches and edges such that each successive vertex is connected by the edge frequently only the vertices are listed especially if there are no parallel edges cycle is path that starts and end at the same vertex simple path is path with distinct vertices directed path is path of only directed edges directed cycle is cycle of only directed edges sub-graph is subset of vertices and edges spanning sub-graph contains all the vertices connected graph has all pairs of vertices connected by at least one path connected component is the maximal connected sub-graph of unconnected graph forest is graph without cycles tree is connected forest (previous type of trees are called rooted treesthese are free treesspanning tree is spanning subgraph that is also tree more properties if is an undirected graph with vertices and edgesif is connected then > if is tree then if is forest then < graph traversal depth first search breadth first search