data structures using graph can be directed or undirected in an undirected graphedges do not have any direction associated with them that isif an edge is drawn between nodes and bthen the nodes can be traversed from to as well as from to figure shows an undirected graph because it does not give figure directed graph any information about the direction of the edges look at fig which shows directed graph in directed graphedges form an ordered pair if there is an edge from to bthen there is path from to but not from to the edge (abis said to initiate from node (also known as initial nodeand terminate at node (terminal nodea graph terminology adjacent nodes or neighbours for every edgee (uvthat connects nodes and vthe nodes and are the end-points and are said to be the adjacent nodes or neighbours degree of node degree of node udeg( )is the total number of edges containing the node if deg( it means that does not belong to any edge and such node is known as an isolated node regular graph it is graph where each vertex has the same number of neighbours that isevery node has the same degree regular graph with vertices of degree is called -regular graph or regular graph of degree figure shows regular graphs ( -regular graph( -regular graph( -regular graphfigure regular graphs closed path vn path path written as { vn)of length from node to is defined as sequence of ( + nodes hereu vn and vi- is adjacent to vi for path is known as closed path if the edge has the same end-points that isif simple path path is known as simple path if all the nodes in the path are distinct with an exception that may be equal to vn if vnthen the path is called closed simple path cycle path in which the first and the last vertices are same simple cycle has no repeated edges or vertices (except the first and last verticesconnected graph graph is said to be connected if for any two vertices (uvin there is path from to that is to say that there are no isolated nodes in connected graph connected graph that does not have any cycle is called tree thereforea tree is treated as special graph (refer fig ( )complete graph (amulti-graph graph is said to be complete if all its nodes are fully connected that isthere is path from one node to every other node in the graph complete graph has ( - )/ edgesa where is the number of nodes in (btree (cweighted graph figure multi-graphtreeand weighted graph clique in an undirected graph (ve)clique is subset of the vertex set vsuch that for every two vertices in cthere is an edge that connects two vertices