Simple Graph Theory

Question 1

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 graph is a collection of points called _____________ and line segments or curves called _________that connect the vertices

Answer 2

vertices or nodes
edges

Question 3

an edge connecting a vertex to itself.

Answer 3

loop

Question 4

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

Answer 4

complete graph

Question 5

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

Answer 5

adjacent

Question 6

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

Answer 6

equivalent

Question 7

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 7

path

Question 8

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

Answer 8

circuit or cycle.

Question 9

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

Answer 9

connected

Question 10

an edge that when you remove makes the graph disconnected.

Answer 10

bridge

Question 11

a vertex is the number of edges attached to it.

Answer 11

degree

Question 12

The diagram below appears in a book in psychology. It is used to indicate ”_________ ” which occur in man- woman relationships.

Answer 12

transactions

Question 13

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.

Answer 13

graph coloring

Question 14

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

Answer 14

chromatic number of the graph.

Question 15

chromatic number of the graph.

Answer 15

Colorable Graph Theorem

Question 16

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

Answer 16

Colorable Graph Theorem.

Question 17

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

Answer 17

Four-Color Theorem

Question 18

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 18

Map Coloring
adjacent

Question 19

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

Answer 19

planar

Question 20

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

Euler path

Question 21

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

Answer 21

Euler path

Question 22

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

Answer 22

Euler circuit

Question 23

A graph that has an Euler circuit is called

Answer 23

Eulerian

Question 24

Eulerian if and only if each vertex has even degree.

Answer 24

connected graph

Question 25

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

Answer 25

Hamiltonian path

Question 26

If the path is closed, it is called

Answer 26

Hamiltonian cycle.

Question 27

If a graph has a Hamiltonian cycle, it is called __________

Answer 27

Hamiltonian

Question 28

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 28

complete graph

Question 29

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

Answer 29

Two Hamiltonian circuits

Question 30

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

Answer 30

tree

Question 31

an undirected, disconnected, acyclic graph. In other words, a disjoint collection of trees is known as forest. Each component of a forest is tree.

Answer 31

forest

Question 32

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 32

spanning tree

Question 33

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

Answer 33

minimum spanning tree

Question 34

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

Answer 34

minimum spanning tree

Question 35

a minimum spanning tree algorithm that takes a graph as input and finds the subset of the edges of that graph which

Answer 35

Prim’s algorithm

Question 36

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 36

planar

Question 37

Four-Color Theorem. The chromatic number of a planar graph is __________.

Answer 37

4

Question 38

used to depict ”what is in conflict with what”, and colors are used to denote the state of a vertex.

Answer 38

GRAPH COLORING

Question 39

the theory of ”partitioning the sets having Internal unreconcilable conflicts.

Answer 39

coloring theory

Question 40

Vertex Coloring: It is a way of coloring the vertices of a graph such that no two adjacent __________ share the same color.

Answer 40

vertices

Question 41

An edge coloring assigns a color to each edge so that no two adjacent edges share the same color.

Answer 41

Edge Coloring

Question 42

a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

Answer 42

face coloring

Question 43

The chromatic number of a graph is the minimum number of colors in a proper coloring of that graph. If chromatic number is r then the graph is r-chromatic.

Answer 43

Chromatic Number

Question 44

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

Answer 44

map coloring

Question 45

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

Answer 45

4