Basic Graphs

Question 1

Handshaking lemma:

1. Formula
2. Parity

Answer 1

The sum of degrees of all nodes is 2x the number of edges.

The number of nodes with odd degree must be even.

Question 2

Complete graph

Notation

Formula edges

Answer 2

K_n

|v| = n

|E| n choose 2

Question 3

Path graph

Notation

Edges

Answer 3

P

N-1 edges

A tree with 2 leaves!

Question 4

Cycle graph

Formula edges

Degrees

Answer 4

C

|v| = |e|

All nodes degree 2

Question 5

Grid graph

Formula vertices

Property degrees and formula

Answer 5

G_m,n

M x N vertices

Corners deg 2, all others 3 or 4

Total degrees: 2mn-m-n

Question 6

Walk

Answer 6

A sequence of nodes linked by edges

LENGTH IS NUMBER OF EDGES

can have repeat nodes

Question 7

Path

Answer 7

A walk where all nodes are distinct

Question 8

Well ordering principle

Answer 8

Every non empty set of numbers has a least element

Question 9

Connectivity

Answer 9

Nodes are connected if there is a walk between them

Reflexive-node connects to self

Transitive - x-y and y-z then x-z

Symmetric: x and y connect to each other

Question 10

Connected component

Answer 10

A subset of nodes that are MAXIMALLY connected and cannot form a bigger group

Question 11

Connected graph

Counting formula

Answer 11

At least one connection.

Number of CCs at MINIMUM nodes-edges

Edges >= nodes-CCs, must be less than nodes choose 2

Question 12

Disconnected graph

Answer 12

More than one CC or edgeless

Question 13

Distance

Answer 13

Shortest path between any 2 nodes