Exam 4

Question 1

A vertex with no edges

Answer 1

Isolated Vertex

Question 2

More than one edge connecting two vertices

Answer 2

Parallel Edges

Question 3

The number of times that a vertex is an endpoint

Answer 3

Degree of a vertex

Question 4

A graph with no loops or parallel edges

Answer 4

Simple Graph

Question 5

A graph that can be partitioned into 2 sets for which every edge connects vertices in different sets

Answer 5

Bipartite Graph

Question 6

The complete bipartite graph on m,n

Answer 6

Kmn

Question 7

A maximal connected subgraph

Answer 7

Connected Component

Question 8

A finite alternating sequence of adjacent vertices and edges

Answer 8

Walk

Question 9

A walk that does not contain a repeated edge

Answer 9

Path

Question 10

A path that does not contain a repeated vertex

Answer 10

Simple Path

Question 11

A walk that begins and ends on the same vertex

Answer 11

Closed Walk

Question 12

A closed walk that does not contain a repeated edge

Answer 12

Circuit

Question 13

Graphs with a 1-1 function such that vertices x and y are joined by an edge and so are f(x) and f(y)

Answer 13

Isomorphic

Question 14

1-1 function between two graphs

Answer 14

Isomorphism

Question 15

A property of a graph that doesn’t change under isomorphism

Answer 15

Invariant

Question 16

A circuit that does not have any other repeated vertex except the first and last

Answer 16

Simple Circuit

Question 17

Circuit which contains every vertex and every edge

Answer 17

Euler Circuit

Question 18

If a graph has an Euler circuit then every vertex has an _____ degree

Answer 18

Even (degree of every vertex in _______)

Question 19

If every vertex is even and the graph is connected, then the graph has _____________

Answer 19

An Euler Circuit (what does this say about connectedness and degrees?)

Question 20

A sequence of adjacent edges and vertices that starts at v, ends at w, and passes through every vertex and along every edge exactly once

Answer 20

Euler Path

Question 21

Connected graph that has no non-trivial circuits

Answer 21

Tree

Question 22

for a tree, the number of edges = __________

Answer 22

The # of vertices in the tree -1

Question 23

A ________ is contained in a tree

Answer 23

Circuitless Graph (is contained in what?)

Question 24

connected AND e=v-1
connected AND circuitless
circuitless AND e=v-1

Answer 24

Properties of a tree

Question 25

A subgraph of a graph that is a tree which includes every vertex

Answer 25

Spanning Tree

Question 26

Graph with numeric weights attached to the edges

Answer 26

Weighted Graph

Question 27

Spanning tree of the least possible weight

Answer 27

Minimal Spanning Tree

Question 28

Algorithm which adds vertices of lowest possible value that do not close circuits

Answer 28

Kruskal's

Question 29

Algorithm that starts with a single vertex, then adds an edge and vertex at each step of minimal weight and does not close a circuit

Answer 29

Prim's

Question 30

Isolated Vertex

Answer 30

A vertex with no edges

Question 31

Parallel Edges

Answer 31

More than one edge connecting two vertices

Question 32

Degree of a vertex

Answer 32

The number of times that a vertex is an endpoint

Question 33

Simple Graph

Answer 33

A graph with no loops or parallel edges

Question 34

Bipartite Graph

Answer 34

A graph that can be partitioned into 2 sets for which every edge connects vertices in different sets

Question 35

Kmn

Answer 35

The complete bipartite graph on m,n

Question 36

Connected Component

Answer 36

A maximal connected subgraph

Question 37

Walk

Answer 37

A finite alternating sequence of adjacent vertices and edges

Question 38

Path

Answer 38

A walk that does not contain a repeated edge

Question 39

Simple Path

Answer 39

A path that does not contain a repeated vertex

Question 40

Closed Walk

Answer 40

A walk that begins and ends on the same vertex

Question 41

Circuit

Answer 41

A closed walk that does not contain a repeated edge

Question 42

Isomorphic

Answer 42

Graphs with a 1-1 function such that vertices x and y are joined by an edge and so are f(x) and f(y)

Question 43

Isomorphism

Answer 43

1-1 function between two graphs

Question 44

Invariant

Answer 44

A property of a graph that doesn't change under isomorphism

Question 45

Simple Circuit

Answer 45

A circuit that does not have any other repeated vertex except the first and last

Question 46

Euler Circuit

Answer 46

Circuit which contains every vertex and every edge

Question 47

Even (degree of every vertex in _______)

Answer 47

If a graph has an Euler circuit then every vertex has an _____ degree

Question 48

An Euler Circuit (what does this say about connectedness and degrees?)

Answer 48

Connected, every vertex has even degree

Question 49

Euler Path

Answer 49

A sequence of adjacent edges and vertices that starts at v, ends at w, and passes through every vertex and along every edge exactly once

Question 50

Tree

Answer 50

Connected graph that has no non-trivial circuits

Question 51

The # of vertices in the tree -1

Answer 51

Number of edges in a tree

Question 52

Circuitless Graph (is contained in what?)

Answer 52

A tree

Question 53

Properties of a tree

Answer 53

connected AND e=v-1 connected AND circuitless circuitless AND e=v-1

Question 54

Spanning Tree

Answer 54

A subgraph of a graph that is a tree which includes every vertex

Question 55

Weighted Graph

Answer 55

Graph with numeric weights attached to the edges

Question 56

Minimal Spanning Tree

Answer 56

Spanning tree of the least possible weight

Question 57

Kruskal's

Answer 57

Algorithm which adds vertices of lowest possible value that do not close circuits

Question 58

Prim's

Answer 58

Algorithm that starts with a single vertex, then adds an edge and vertex at each step of minimal weight and does not close a circuit