graphs

Question 1

subgraph

Answer 1

part of the original graph

Question 2

spanning tree

Answer 2

a subgraph which includes all of the vertices of the original graph

Question 3

walk

Answer 3

route through graph from on vertex to the next along edges

Question 4

path

Answer 4

a walk in which no vertex is visited more than once

Question 5

trail

Answer 5

no edges visited more than once

Question 6

cycle

Answer 6

a walk that starts and ends at the same vertex and no other vertex is visited more than once

Question 7

node’s degree (odd or even)

Answer 7

the number of edges attached to it

Question 8

Hamiltonian cycle

Answer 8

a cycle that includes every vertex

Question 9

eulerian cycle

Answer 9

a trail that traverses every arc (once) and starts and ends at the same vertex

Question 10

tree

Answer 10

connected graph with no cycles

Question 11

graph

Answer 11

points /vertices/nodes
connected by
lines/edges/arcs

Question 12

connected graph

Answer 12

a path can be found between any two vertices

Question 13

loop

Answer 13

an edge which starts and ends at the same vertex

Question 14

what’s a simple graph?

Answer 14

no loops
(there aren’t multiple edges connecting the same two vertices)

Question 15

diagraph/directed graoh

Answer 15

edges have a given direction

Question 16

handshaking lemma

Answer 16

the sum of the degrees of the vertices = 2x number of edges
(on an undirected graph)