Simple Graph Theory Concepts Flashcards
collection of points called vertices or nodes
graph
line segments or curves that connect
the vertices.
edges
an edge connecting a vertex to itself.
loop
graph that has an edge
connecting every pair of vertices.
complete graph
Two vertices are ______ if there is an edge joining
them.
adjacent
Graphs are considered as ______ if they have same
vertices connected in the same way.
equivalent
alternating sequence of vertices and edges.
path
If a path begins and ends with the same vertex
closed path or a circuit or cycle
if for any two vertices, there is at
least one path that joins them.
connected
an edge that when you remove makes the
graph disconnected.
bridge
vertex is the number of edges attached
to it.
degree
to color the vertices or edges
graph coloring
smallest number of colors required to color the
vertices of a graph is the
chromatic number of the graph
no circuits that consist of odd number of
vertices.
2- Colorable Graph Theorem
planar graph is at most 4.
Four-Color Theorem
with the different regions as vertices.
map
graph representing a map
planar
passes through every edge exactly once only
Euler path
closed path that contains all the edges of the graph.
Euler circuit
graph that has an Euler circuit
Eulerian
each vertex has even degree.
connected graph
graph is a path passing through each vertex of the graph exactly once.
Hamiltonian path
If the path is closed, it is called
Hamiltonian cycle
If a graph has a Hamiltonian cycle, it is called
Hamiltonian
graph in which any two vertices are connected by exactly one path.
tree
