Simple Graph

Question 1

It is a collection of points called vertices or nodes and line segments or curves called edges that connect the vertices.

Answer 1

Graph

Question 2

A ____ is an edge connecting a vertex to itself.

Answer 2

loop

Question 3

A ___________ is a graph that has an edge connecting every pair of vertices.

Answer 3

complete graph

Question 4

Two vertices are _______ if there is an edge joining them.

Answer 4

Adjacent

Question 5

Graphs are considered as ________ if they have same vertices connected in the same way.

Answer 5

equivalent

Question 6

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.

Answer 6

Path

Question 7

If a path begins and ends with the same vertex, it is a closed path or a __________.

Answer 7

circuit or cycle

Question 8

A graph is ________ if for any two vertices, there is at least one path that joins them.

Answer 8

connected

Question 9

A _______ is an edge that when you remove makes the
graph disconnected.

Answer 9

bridge

Question 10

The _______ of a vertex is the number of edges attached to it.

Answer 10

degree

Question 11

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.

Answer 11

graph coloring

Question 12

The smallest number of colors required to color the vertices of a graph is the

Answer 12

chromatic number of the graph

Question 13

A graph is 2-colorable if andonly if it has no circuits that consist of odd number of vertices.

Answer 13

2- Colorable Graph Theorem

Question 14

The chromatic number of a planar graph is at most 4.

Answer 14

Four-Color Theorem

Question 15

A map can be represented by a graph with the different regions as vertices. Two regions are __________ if they share part of their boundaries.

Answer 15

adjacent

Question 16

The graph representing a map is _______. Hence, it needs only 4 colors.

Answer 16

planar

Question 17

• 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

Answer 17

Euler path

Question 18

A graph has an _________ if and only if no more than two of its vertices have odd degree.

Answer 18

Euler path

Question 19

An ____________of a graph is a closed path that contains all the edges of the graph.

Answer 19

Euler circuit

Question 20

A graph that has an Euler circuit is called _______.

Answer 20

Eulerian

Question 21

A ____________ is Eulerian if and only if each vertex
has even degree.

Answer 21

connected graph

Question 22

A __________________ of a graph is a path passing through
each vertex of the graph exactly once.

Answer 22

Hamiltonian path

Question 23

If the path is closed, it is called a ______________.

Answer 23

Hamiltonian cycle

Question 24

If a graph has a Hamiltonian cycle, it is called
______________.

Answer 24

Hamiltonian

Question 25

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)!.

Answer 25

complete graph

Question 26

are the same if they pass through the same vertices in the same order, regardless of the vertex where they begin and end.

Answer 26

Two Hamiltonian circuits

Question 27

A ______ is a graph in which any two vertices are
connected by exactly one path.

Answer 27

tree

Question 28

What are the 4 Properties of Trees?

Answer 28

1. A tree has no circuits.
2. Trees are connected graphs.
3. Every edge in a tree is a bridge.
4. A tree with n vertices has exactly n-1 edges.

Question 29

a ________ is an undirected, disconnected, acyclic graph.

Answer 29

forest

Question 30

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.

Answer 30

spanning tree

Question 31

A _____________ tree for a weighted graph is the
spanning tree for the graph that has the smallest
possible sum of the weights.

Answer 31

minimum spanning

Question 32

A ________ tree must have one fewer edge than
the number of vertices.

Answer 32

minimum spanning

Question 33

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.

Answer 33

planar