Chapter 5: Mathematics of Graphs

Question 1

Trees in electric Circuits made by

Answer 1

Gustav Krichoff

Question 2

Enumeration of Chemical Isomers by

Answer 2

• Arthur Cayley
• James J. Sylvester
• George Polya

Question 3

Four Colors of Maps by

Answer 3

• Francis Guthrie
• Auguste De Morgan

Question 4

Most common Known Applications of Graph Theory

Answer 4

• Transportation networks
• Internet
• Genetic interaction network
• Ecological networks

Question 5

• Are points in a graph
• Non-empty set of elements

Answer 5

Vertices

Question 6

• Are lines in a graph
• Family of two element subsets of V(G)

Answer 6

Edges

Question 7

• set V(G)

Answer 7

Vertex set

Question 8

• set E(G)

Answer 8

Edge set

Question 9

• If e = uv is an edge in G, u and v are ______

Answer 9

adjacent vertices

Question 10

• Adjacent vertices in an edge G are ____ with each other

Answer 10

incident

Question 11

• Number of edges connected with a vertex as an end-vertex

Answer 11

Degree of a vertex

Question 12

• Graphs without multiple edges or self-loops

Answer 12

Simple graph

Question 13

• When 2 vertices must be written twice because there are two edges connecting 1 and 2

Answer 13

Multiple edges

Question 14

• Edge joining it and itself

Answer 14

Loop

Question 15

• multiple edges but no loops

Answer 15

Multigraph

Question 16

• loops and multiple edges

Answer 16

Pseuodograph

Question 17

• if every pair of points can be joined by an edge

Answer 17

Connected graph

Question 18

• if an edge does not join every pair of points

Answer 18

Disconnected graph

Question 19

Eulerian is if and only if

Answer 19

• degree of each vertex of G is even.
• graph is a Euler circuit

Question 19

• path using every edge of the graph G exactly once

Answer 19

Euler path

Question 20

• if and only if the degree of each vertex of G is even.

Answer 20

Eulerian

Question 21

• Euler path that returns to its start

Answer 21

Euler circuit

Question 22

invented Icosian game

Answer 22

Sir William Rowan Hamilton

Question 23

What year did the Icosian game get invented

Answer 23

1857

Question 24

• puzzle-game involved hunting for Hamiltonian cycle
• distributed as a dodecahedron graph with a hole at each vertex.

Answer 24

Icosian game

Question 25

• polyhedron with twelve flat faces

Answer 25

Dodecahedron

Question 26

• graph G is a path which visits every vertex in G exactly once

Answer 26

Hamilton path

Question 27

Hamiltonian is if and only if

Answer 27

• the graph has a Hamilton circuit.

Question 28

• Hamilton path that returns to its start.

Answer 28

Hamiltonian circuit

Question 29

• Graph in which edge is associated with a value

Answer 29

Weighted graph

Question 30

• Value in a weighted graph

Answer 30

Weight

Question 31

• from vertex u to vertex v is a sequence of adjacent edges starting u and ending in v such that the end of each edge other than the last one is the start of the next edge in the sequence.

Answer 31

Path

Question 32

• sum of the weights of the edges of the path.

Answer 32

Length of a path

Question 33

• Dutch computer scientist from Netherlands
• Developed an algorithm that finds the shortest path between vertices in a connected weighted graph

Answer 33

Edsger Wybe Dijkstra (May 11, 1930 – August 6, 2002)

Question 34

• an assignment of colors to its vertices so that no two adjacent vertices have the same color

Answer 34

Coloring of a graph