SIMPLE GRAPH

Question 1

A graph is a collection of points called ______or_________
and line segments or curves called _______that connect
the vertices.

Answer 1

1.) Vertices or Nodes
2.) Edges

Question 2

An edge connecting a vertex to itself.

Answer 2

Loop

Question 3

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

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

A Path

Question 7

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

Answer 7

Circuit or Cycle

Question 8

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

Answer 8

Degree

Question 9

A ___________is an edge that when you remove makes the
graph disconnected

Answer 9

Bridge

Question 10

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

Answer 10

chromatic number of the graph

Question 11

A graph is 2-colorable if and only if it has_________that consist of ______________

Answer 11

1.) No circuits
2.) Odd number of vertices

Question 12

The chromatic number of a planar graph is atmost 4.

Answer 12

Four-Color Theorem

Question 13

The graph representing a map is planar. Hence, it needs
only ____ colors.

Answer 13

1.) 4

Question 14

• 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 14

Euler path

Question 15

a closed path that contains all the edges of the graph.

Answer 15

Euler circuit

Question 16

A graph that has an Euler circuit is called

Answer 16

Eulerian

Question 17

If all vertices are even, the graph has at least ____Euler
circuit

Answer 17

1

Question 17

A connected graph is Eulerian if and only if each vertex
has ______degree.

Answer 17

Even

Question 18

If there are more than two odd vertices, the graph
has __Euler path and ___ Euler circuits

Answer 18

NO
NO

Question 18

If exactly two vertices are odd, the graph has no
Euler circuits but at least ____ Euler path.

Answer 18

One

Question 19

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

Answer 19

Hamiltonian path

Question 20

If a graph has a Hamiltonian cycle, it is called

Answer 20

Hamiltonian.

Question 21

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

Answer 21

A tree

Question 22

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 22

spanning tree

Question 22

Properties of Trees:

Answer 22

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 22

an undirected, disconnected, acyclic graph.

In other words, a disjoint collection of trees is known as _______. Each component of a _______ is tree.

Answer 22

FOREST