graph

Question 1

is a city on the Pregel river in Prussia
- The city occupied two islands plus areas on both banks

Answer 1

Königsber Bridge Problem

Question 2

the greatest mathematician
that Switzerland has ever
produced

Answer 2

LEONHARD EULER

Question 3

A branch of mathematics concerning with network of
points connected by lines (Carlson, 2020).
• It is ultimately the study of relationships (Flovik, 2020).

Answer 3

mathematics of graph

Question 4

: a region

Answer 4

A vertex

Question 5

: a path(bridge) between two regions

Answer 5

An edge

Question 6

A relation between an edge and a pair of vertices

Answer 6

graph

Question 7

The number of vertices in G, 𝑣(𝐺)

Answer 7

order

Question 8

The number of edges in G, 𝑒(𝐺)

Answer 8

size

Question 9

𝑽(𝑮 )

Answer 9

vertex set

Question 10

𝑬(𝑮 )

Answer 10

edge set

Question 11

An edge whose endpoints are equal

Answer 11

loop

Question 12

Edges have the same pair of endpoints

Answer 12

multiple edges

Question 13

A graph has no loops or multiple edges

Answer 13

Simple graph

Question 14

Two vertices are ___ and are ___if they are
the endpoints of an edge

Answer 14

adjacent, neighbors

Question 15

a graph whose vertex set and edge set are
finite

Answer 15

finite graph

Question 16

the graph whose vertex set and edges are
empty

Answer 16

null graph

Question 17

the edges form
the same connections of vertices in each graph.

Answer 17

equivalent graphs

Question 18

A simple graph
• 𝑉(𝐺’) = 𝑉(𝐺)
• 𝐸(𝐺’) = { 𝑢𝑣 | 𝑢𝑣 𝐸(𝐺) }

Answer 18

complement

Question 19

a set of pairwise adjacent vertices (a
complete subgraph)

Answer 19

Clique in a graph

Question 20

a set of pairwise
nonadjacent vertices

Answer 20

independent set in a graph

Question 21

if 𝑽(𝑮) is the union of two disjoint
independent sets called partite sets of 𝑮
- The vertices can be partitioned into two sets such
that each set is independent

Answer 21

bipartite graphs

Question 22

the
minimum number of colors needed to label the vertices
so that adjacent vertices receive different colors
- X(G) = 3

Answer 22

chromatic number

Question 23

a partition of the plane into connected regions

Answer 23

map

Question 24

Two committees can not hold meetings at the same time
if two committees have common member

Answer 24

SCHEDULING AND
GRAPH COLORING

Question 25

a sequence of distinct vertices such that two consecutive vertices are adjacent

Answer 25

path

Question 26

a closed Path

Answer 26

cycle

Question 27

The assignment of endpoints to edges in H is the same as in G

Answer 27

subgraph

Question 28

There exists at least one path between two vertices

Answer 28

connected

Question 29

there is no path between two vertices

Answer 29

disconnected

Question 30

The vertices vj and vk

Answer 30

adjacent

Question 31

The edge ei is said to be ___upon vj

Answer 31

incident

Question 32

vertex vk is the number of edges incident upon vk . It is denoted as d(vk)

Answer 32

Degree

Question 33

the n-by-n matrix in which entry ai,j is the number of edges in G with endpoints {vi , vj}

Answer 33

adjacency matrix

Question 34

the n-by-m matrix in which entry mi,j is 1 if vi is an endpoint of ei and otherwise is 0

Answer 34

incidence matrix

Question 35

a simple graph whose vertices are pairwise adjacent

Answer 35

complete graph

Question 36

is a simple bipartite graph such that two vertices are adjacent if and only if they are in different partite sets.

Answer 36

biclique or complete bipartite graph

Question 37

list of vertices and edges v0 , e1 , v1 , …., ek , vk such that, for 1  i  k, the edge ei has endpoints vi-1 and vi .

Answer 37

walk

Question 38

a walk with no repeated edge.

Answer 38

trail

Question 39

graph with vertex degrees all even.

Answer 39

EVEN GRAPH

Question 40

vertex is odd [even] when its degree is odd?

Answer 40

odd graph/ odd vertex

Question 41

graph that can be drawn without any breaks in the curve without repeating any edge. • A graph with more than two odd vertices is NOT traversable.

Answer 41

TRAVERSABLE GRAPH

Question 42

it has a closed traversable trail. • Theorem: A graph G is Eulerian if and only if each vertex has an even degree

Answer 42

Eulerian Graph

Question 43

A graph with a closed path that passes through all vertices exactly once.

Answer 43

HAMILTONIAN GRAPH

Question 44

when we do not specify the first vertex but keep the list in cyclic order.

Answer 44

circuit

Question 45

graph is a circuit or trail containing all the edges.

Answer 45

Eulerian circuit or Eulerian trail

Question 46

circuit that uses every edge, but never uses the same edge twice, is called an

Answer 46

euler circuits

Question 47

a path that uses every edge once and only once

Answer 47

euler path

Question 48

This path visits each vertex once and returns to the starting vertex without visiting any vertex twice.

Answer 48

Hamiltonian circuit.

Question 49

Consider a connected graph with at least three vertices and no multiple edges. Let 𝑛 be the number of vertices in the graph. If every vertex has degree of at least 𝑛 2 , then the graph must be Hamiltonian.

Answer 49

dirac's theorem

Question 50

is so called because it has us choose the “cheapest” option at every chance we get

Answer 50

greedy algorithm

Question 51

Use the ____ to find a Hamiltonian circuit

Answer 51

edge-picking algorithm