Module 11 Vocab

Question 1

Undirected Graph (notation)

11.1

Answer 1

G = (V, E)

V = vertices/nodes and E = edges

Question 2

Undirected Graph (words)

11.1

Answer 2

A pair of finite sets
first set represents vertices/nodes
second set represents edges

Question 3

Vertices/Nodes

11.1

Answer 3

V: finite, non-empty set of vertices/nodes

.

Question 4

Edges (notation)

11.1

Answer 4

E ⊆ 2^v

Question 5

Edges (definition)

11.1

Answer 5

set of nodes of cardinality 2

Question 6

Edges (words)

11.1

Answer 6

finite (possibly empty) set of edges consisting only of subsets of cardinality 2

Question 7

Edges and Incident

11.1

Answer 7

Each edge is incident to exactly two vertices

Question 8

If V = {1, 2, 3} how many possible edges can graph G have?

11.1

Answer 8

3 edges:
{1, 2} {1, 3} {2, 3}

Question 9

u - v or v-u

11.1

Answer 9

represents the edge for {u, v}
tells us that u and v are linked by an edge

Question 10

Vertices and u and v are — by —

11.1

Answer 10

linked
an edge

Question 11

Incident

11.1

Answer 11

the edge is incident to its endpoints (vertices)
“the edge u-v is incident to u and v”

Question 12

Adjacent/Neighbors

11.1

Answer 12

two vertices that share an edge

Ex: u-v are adjacent

Question 13

Degree

11.1

Answer 13

degree of a vertex:
the number of neighbors of a vertex

Question 14

Degree (notation)

11.1

Answer 14

deg(u)
the number of vertices adjacent to u

Question 15

Isolated

11.1

Answer 15

a vertex of degree 0
no neighbors

Question 16

Handshaking Lemma

11.1

Answer 16

the sum of the degrees of all nodes in a graph is twice the number of edges

Question 17

Handshaking Lemma (notation)

11.1

Answer 17

Σ{v∈V} deg(v) = 2|E|

Question 18

add up the degrees of all the nodes and it’s equal to 2 times the number of edges

11.1

Answer 18

Handshake Lemma

Question 19

In the handshake lemma, what does every part of the metaphor represent?

11.1

Answer 19

people: nodes/vertices
number of people each person shakes hands with: degrees
handshake: edge

Question 20

Handshake Lemma (proof)

11.1

Answer 20

since each edge is incident to exactly two vertices, each edge contributes two to the sum of degrees of the vertices

Question 21

Number of vertices of odd degree proposition

11.1

Answer 21

in any graph there are an EVEN number of vertices of odd degree

Question 22

Even number of vertices with odd degree proof

11.1

Answer 22

Σ{v∈V} deg(v) = Σ{v∈V_e} deg(v) + Σ{v∈V_o} deg(v)

LHS: handshaking RHS: rule of thumb

Question 23

In the graph G = (V, E) all vertices have degree 1. How many vertices can G have?

11.1

Answer 23

since every vertex has 1 degree,
sum of all degrees = |V|
handshake says: |V| = 2|E|
so must have even number of vertices

Question 24

What are two ways you can calculate the sum of degrees?

11.1

Answer 24

way 1: add degrees of all vertices
way 2: count edges and multiply by 2

Question 25

G = (V, E) and all vertices have an even degree. Can G have as many vertices as we wish?

11.1

Answer 25

Yes with an endless graph where each of the n vertices has 0 edges (and thus 0 degree) since 0 is even

Question 26

Edgeless Graphs

11.2

Answer 26

some vertices and no edges
|V| ≥ 1
E = ∅ and |E| = 0

Question 27

Complete Graphs (notation)

11.2

Answer 27

K_n = (V, E) where |V| = n
and E = {{u,v} | u,v ∈ V u≠v}

Question 28

Complete Graphs

11.2

Answer 28

1. has edges between any two vertices
2. has the maximum number of edges
3. no isolated vertices

Question 29

Complete Graphs (# of edges)

11.2

Answer 29

(n choose 2)

Question 30

Path Graphs (notation)

11.2

Answer 30

P_n where there are n≥1 vertices

Question 31

Path Graphs (# of edges)

11.2

Answer 31

n-1

Question 32

Path Graphs

11.2

Answer 32

vertices are arranged “in a row”

for n≥2, 2 vertices have degree 1 (endpoints) and all other vertices have degree 2

Question 33

Cycle Graphs (notation)

11.2

Answer 33

C_n where n≥1 vertices

Question 34

Cycle Graphs (# of edges)

11.2

Answer 34

n = # of vertices = # of edges

Question 35

Cycle Graphs

11.2

Answer 35

vertices are arranged “in a circle”
all vertices have degree 2

Note: C_1 and C_2 are not defined

Question 36

Grid Graphs (notation)

11.2

Answer 36

m x n
m = # of rows
n = # of vertices
m,n ≥ 1

Question 37

Grid Graphs (number of edges)

11.2

Answer 37

2mn - m - n

Question 38

Grid Graphs

11.2

Answer 38

each vertex is linked by an edge to the vertices “closest” to it

Question 39

Grid Graphs (# of vertices)

11.2

Answer 39

mn vertices

Question 40

If all vertices in a graph G have degree 2, must G be a cycle graph?

11.2

Answer 40

No!
but it’s essentially made up of two (or more) cycles

Question 41

Walks

11.3

Answer 41

a non-empty sequence of vertices consecutively linked by edges

Question 42

Walks (notation)

11.3

Answer 42

u0 — u1— ··· — uk

Question 43

Endpoints

11.3

Answer 43

u0 and uk of the walk
u0 — u1— ··· — uk

Question 44

Connected

11.3

Answer 44

u0 and uk are connected by the walk
u0 — ··· — uk

Question 45

Length

11.3

Answer 45

number of edges of the wal(k)

Question 46

Paths

11.3

Answer 46

a walk with distinct vertices
walks of length 0 or 1 are also paths

ex: 1- 2 - 4 NON-ex: 1 - 2 - 3 - 4 - 2 - 5

Question 47

Well-Ordering Principle

11.3

Answer 47

every non-empty set of natural numbers has a least element (smallest element)

Question 48

Walk-Path Proposition I

11.3

Answer 48

for any walk, length n≥3 with distinct endpoints, there is a path with length ≤ n

Question 49

Walk-Path Proposition I Implies

11.3

Answer 49

the shortest walk connecting u0 to un must be a path

Question 50

Why is the shortest walk a path?

11.3

Answer 50

cut off the cycle from the walk and replace it with a node (walk length 0)

Question 51

Walk-Path Proposition II

11.3

Answer 51

if there is a walk, with length n≥3 and distinct endpoints, there is a path whose sequence of nodes and edges is a subsequence of the sequence of nodes and edges of the walk

*subsequence preserves order but doesn’t have to be consecutive

Question 52

What’s the maximum length of a path in Cn? In Kn?

11.3

Answer 52

Cn = cycle = n-1
Kn = complete = n-1

Question 53

If u∈C1 and v∈C2 and u— ··· — v and C2 is maximally connected, why must u∈C2?

11.4

Answer 53

Since u is connected to v, C2 must incldue vertex u. If u wasn’t in C2, then there would be a bigger set of vertices C’ (C2 plus the element u) for which any two vertices are connected and thus C2 wouldn’t be maximally connected.

Question 54

Connected (notation)

11.4

Answer 54

u — ··· — v

Question 55

Connected (definition)

11.4

Answer 55

two vertices, u and v, are connected if there exists some walk/path with endpoints u and v

Question 56

Connectivity Relaion

11.4

Answer 56

— ··· —

Question 57

Reflexive (notation)

11.4

Answer 57

u — ··· — u

Question 58

Reflexive (words)

11.4

Answer 58

a vertex is connected to itself by a walk/path of length 0

Question 59

Symmetric (notation)

11.4

Answer 59

if u— ··· —v, then v— ··· —u

Question 60

Symmetric (words)

11.4

Answer 60

if u is connected to v, then v is connected to u

Question 61

Transitive (notation)

11.4

Answer 61

if u— ··· —v and v— ··· —w, then u— ··· —w

Question 62

Transitive (words)

11.4

Answer 62

if u is connected to v and v is connected to w, then u is connected to w

think: concatenate

Question 63

Concatenating walks and paths

11.4

Answer 63

the concatenation of walks is also a walk BUT the concatenation of paths need not be a path

Question 64

Can A⟂A?

11.4

Answer 64

nope, impossible
justification: A∩A ≠ A x A

Question 65

Connected Component

11.4

Answer 65

a set of vertices C∈V
1) any two vertices in C are connected
2) there is no strictly bigger set of vertices such that any two vertices of C’ are connected

Question 66

Maximally Connected

11.4

Answer 66

set that contains all the vertices that are connected
(no other set contains more of the connected vertices)

ex: {1,2,4} vs. {1, 2, 3, 4}

Question 67

Partition Proposition

11.4

Answer 67

any two distinct connected components are disjoint
(even if its just by itself)

Question 68

Connected Graph

11.4

Answer 68

has exactly one connected component
ex: complete, path, cycle, mxn

Question 69

Disconnected Graph

11.4

Answer 69

has two or more connected components
ex: edgeless (more than 1)

Question 70

Distance

11.4

Answer 70

the length of the shortest path between two vertices

Question 71

“Degree of separation”

11.4

Answer 71

(in social networks)
the number of intermediate nodes on the shortest path

ex: 6 degrees of separation = graph distance 7

Question 72

Shortest Path

Self

Answer 72

in an mxn grid graph, every path of mininum length from (0,0) to (n-1, m-1) has length m+n-2 and traverses edges only upwards or rightwards