Terminologies Flashcards
Size of Graph
Cardinality of Edge set
Order of Graph
Cardinality of Vertex Set
Adjacent Edges
Two edges are adjacent if they have are incident on a common vertex
Subgraph
H is a subgraph of G if
V(H) is a subset of V(G)
and E(H) is a subset of E(G)
Improper Subgraph
Every graph is a subgraph of itself, and since it is equal, it is an improper subgraph
Proper Subgraph
A graph H that is a subgraph of graph G, and H!=G is called a proper subgraph
Spanning Subgraph
A subgraph H is a spanning subgraph of G is if V(H)=V(G) and E(H) is a subset of E(G)
Vertex induced subgraph
a subgraph of a given graph that contains a subset of the vertices of the original graph and all the edges that are present between those vertices.
Edge induced subgraph
A subgraph of a given graph that contains a subset of the edges of the original graph and the vertices incident to those edges
Walk
A walk in a graph is a sequence of vertices where consecutive vertices in the sequence are adjacent.
A walk can repeat vertices and edges
Path
If a walk does not repeat any edges and vertices, it’s called a path.
Trail
A walk in which you cannot repeat edges.
Closed Walk, Path or Trail
If a walk, path or trail that starts and ends at same vertex is a closed walk/path/trail
Circuit
A closed trail
Cycle or simple cycle
A cycle, often referred to as a simple cycle, is a closed path where no vertex (except for the starting and ending vertex) and no edge are repeated.
