SIMPLE GRAPH Flashcards
A graph is a collection of points called ______or_________
and line segments or curves called _______that connect
the vertices.
1.) Vertices or Nodes
2.) Edges
An edge connecting a vertex to itself.
Loop
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
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.
A Path
If a path begins and ends with the same vertex, it is a
closed path or a________or_________.
Circuit or Cycle
The __________of a vertex is the number of edges attached
to it.
Degree
A ___________is an edge that when you remove makes the
graph disconnected
Bridge
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 and only if it has_________that consist of ______________
1.) No circuits
2.) Odd number of vertices
The chromatic number of a planar graph is atmost 4.
Four-Color Theorem
The graph representing a map is planar. Hence, it needs
only ____ colors.
1.) 4
- 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 closed path that contains all the edges of the graph.
Euler circuit
A graph that has an Euler circuit is called
Eulerian
If all vertices are even, the graph has at least ____Euler
circuit
1
A connected graph is Eulerian if and only if each vertex
has ______degree.
Even
If there are more than two odd vertices, the graph
has __Euler path and ___ Euler circuits
NO
NO
If exactly two vertices are odd, the graph has no
Euler circuits but at least ____ Euler path.
One
a graph is a path passing through
each vertex of the graph exactly once.
Hamiltonian path
If a graph has a Hamiltonian cycle, it is called
Hamiltonian.
a graph in which any two vertices are
connected by exactly one path.
A tree
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
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
an undirected, disconnected, acyclic graph.
In other words, a disjoint collection of trees is known as _______. Each component of a _______ is tree.
FOREST