graph

Question 1

Circuit

Answer 1

starts and ends in the same vertex

Question 2

Path

Answer 2

any path between two vertices

Question 3

Euler

Answer 3

Goes through every edge in the graph

Question 4

Hamilton

Answer 4

goes through every vertex in the graph.

Question 5

simple graph

Answer 5

not more than two edges connecting the same vertices

Question 6

Kn

Answer 6

Complete graph:

every vertex is connected to every other vertex

Question 7

Cn

Answer 7

Cycle:

triangle, square, pentagon, hexagon,

Question 8

Bipartite graph:

Answer 8

V1 and V2, each edges ONLY connects one V1 element, and one V2 element.

Question 9

How to determine if bipartite:

Answer 9

A graph is bipartite if and only if it is not possible to start
at a vertex and return to this vertex by traversing an odd
number of distinct edges.
ODD: not bipartite

Question 10

strongly connected:

Answer 10

There is a path to every vertex from every vertex, otherwise weakly connected
if there’s “two” graph, not weakly connected

Question 11

Euler circuit

Answer 11

Exists when it only has even degree vertices

Question 12

Euler path

Answer 12

Exists if there is only two vertices of odd degree

Question 13

Hamilton circuit

Answer 13

If G is a simple graph with n ≥ 3, then G has a Hamilton circuit
if the degree of each vertex is at least n/2

Question 14

hamilton path:

Answer 14

If G is a simple graph with n ≥ 3, then G has a Hamilton circuit if
d(u) + d(v) >= n for every pair of non adjacent vertices u and v

Question 15

K m,n

Answer 15

every vertex of V1 (m) goes to every element of V2 (n)