Simple Graph Flashcards
It is a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices.
Graph
A ____ is an edge connecting a vertex to itself.
loop
A ___________ is a 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
A ______ is an alternating sequence of vertices and edges. It can be seen as a trip from one vertex to another using the edges of a graph.
Path
If a path begins and ends with the same vertex, it is a closed path or a __________.
circuit or cycle
A graph is ________ if for any two vertices, there is at least one path that joins them.
connected
A _______ is an edge that when you remove makes the
graph disconnected.
bridge
The _______ of a vertex is the number of edges attached to it.
degree
The idea is to color the vertices or edges of a graph in such a way that adjacent vertices or concurrent edges are given different colors.
graph coloring
The smallest number of colors required to color the vertices of a graph is the
chromatic number of the graph
A graph is 2-colorable if andonly if it has no circuits that consist of odd number of vertices.
2- Colorable Graph Theorem
The chromatic number of a planar graph is at most 4.
Four-Color Theorem
A map can be represented by a graph with the different regions as vertices. Two regions are __________ if they share part of their boundaries.
adjacent
The graph representing a map is _______. Hence, it needs only 4 colors.
planar
- a path that passes through every edge exactly once only
- a path that contains all the edges of the graph
- begin and end with the odd-degree vertices
Euler path
A graph has an _________ if and only if no more than two of its vertices have odd degree.
Euler path
An ____________of a graph is a closed path that contains all the edges of the graph.
Euler circuit
A graph that has an Euler circuit is called _______.
Eulerian
A ____________ is Eulerian if and only if each vertex
has even degree.
connected graph
A __________________ of a graph is a path passing through
each vertex of the graph exactly once.
Hamiltonian path
If the path is closed, it is called a ______________.
Hamiltonian cycle
If a graph has a Hamiltonian cycle, it is called
______________.
Hamiltonian
Every ________________ with more than two vertices has a Hamiltonian circuit. Furthermore, the number of Hamiltonian circuits in a complete graph with n vertices is (n-1)!.
complete graph
are the same if they pass through the same vertices in the same order, regardless of the vertex where they begin and end.
Two Hamiltonian circuits
A ______ is a graph in which any two vertices are
connected by exactly one path.
tree
What are the 4 Properties of Trees?
- A tree has no circuits.
- Trees are connected graphs.
- Every edge in a tree is a bridge.
- A tree with n vertices has exactly n-1 edges.
a ________ is an undirected, disconnected, acyclic graph.
forest
A __________ for a graph is a tree that results from
the removal of as many edges as possible from the
original graph without making it disconnected.
spanning tree
A _____________ tree for a weighted graph is the
spanning tree for the graph that has the smallest
possible sum of the weights.
minimum spanning
A ________ tree must have one fewer edge than
the number of vertices.
minimum spanning
A graph is _________ if it can be drawn in such a way that no
edges cross. This means that any two edges can meet
only at an endpoint.
planar
