Exam 2

Question 1

Vertices

Answer 1

Dots

Question 2

Edges

Answer 2

Lines

Question 3

Adjacent Vertices

Answer 3

Two vertices that are connected with an edge.

Question 4

Isomorphic

Answer 4

A function that renames the vertices (dots) between two edges (lines)

Question 5

Bijection

Answer 5

An isomorphism between two graphs

Question 6

Isomorphism Class

Answer 6

Collection of isomorphic graphs

Question 7

Induced Subgraph

Answer 7

Smaller graph of a larger one formed by choosing some vertices but all the edges in between them

Question 8

Multigraph

Answer 8

Double edges or Single loops

Question 9

Find number of edges

Answer 9

1) Sum of Degree: (Vertices * 2)

2) SoD = 2 * Number of Edges

3) NoE = SoD/2

Question 10

Handshaking Lemma

Answer 10

Sum of Degrees (Vertices * 2) = 2 * Number of Edges

Question 11

Tree

Answer 11

Connected Graph with no cycles

Question 12

Forest

Answer 12

Multiple Trees

Question 13

Rooted Tree

Answer 13

One vertex that a section of the tree is directed away from

Question 14

Proposition 2.2.2

Answer 14

A graph is a tree if there is only one distinct path connecting them

Question 15

Corollary 2.2.3

Answer 15

If you pick any two vertices in a forest, there can be at most one path connecting them.

A leaf is a vertex that is connected to exactly one other vertex by a single edge.

Question 16

Degree of a vertex

Answer 16

Number of edges connected

Question 17

Proposition 2.2.4

Answer 17

A tree with two or more vertices must have at least two leaves.

Leaves are vertices with degree one, meaning they are connected to only one other vertex.

Question 18

Proposition 2.2.5

Answer 18

You will always have 1 less edges vs vertexes
E = V-1

Question 19

Theorem 2.2.7

Answer 19

Every connected graph has a spanning tree.

Question 20

Spanning Tree

Answer 20

A subgraph of a graph that is a tree, containing all vertexes in a line

Question 21

Smallest/Largest number of edges to remove from Spanning Graph

Answer 21

1) Vertexes - 1 = Edges
2) Given number of edges - Found Edges

Question 22

Euler Path

Answer 22

A path in a graph that travels through every edge exactly once but doesn’t have to return to the starting point.

Every vertex in the graph must have an even number of edges (even degree or even amount of edges)

Question 23

Euler Circuit

Answer 23

A special type of Euler Path where you travel through every edge exactly once and return to the starting point.

All vertices must have an even degree (even number of edges).

Question 24

Lattice Path

Answer 24

One of the shortest paths (Horiz or Vert only) connecting two paths on the Lattice (integers only)

Question 25

Lattice

Answer 25

Only coordinates with integers