Simple Graph Theory Flashcards
a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices.
graph
A graph is a collection of points called _____________ and line segments or curves called _________that connect the vertices
vertices or nodes
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.
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
an edge that when you remove makes the graph disconnected.
bridge
a vertex is the number of edges attached to it.
degree
The diagram below appears in a book in psychology. It is used to indicate ”_________ ” which occur in man- woman relationships.
transactions
One of the subjects studied by mathematicians is _________. 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
chromatic number of the graph.
chromatic number of the graph.
Colorable Graph Theorem
A graph is 2-colorable if and only if it has no circuits that consist of odd number of vertices.
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.
Map Coloring
adjacent