General Definitions

Question 1

Order

Answer 1

Number of Vertices

Question 2

Size

Answer 2

Number of Edges

Question 3

Simple Graph

Answer 3

No loops or mult. edges

Question 4

K-Regular

Answer 4

All vertices have degree k

Question 5

Trail

Answer 5

Walk w/ distinct edges

Question 6

Path

Answer 6

Walk w/ distinct vertices

Question 7

Euler Circuit

Answer 7

A path containing every edge

Question 8

Eulerian Theorem

Answer 8

A graph is Eulerian IFF it is even and has at most 1 nontrivial component. (Proof by Maximality)

Question 9

Independent Set

Answer 9

Set of non-pairwise adjacent vertices

Question 10

Clique

Answer 10

Set of vertices s.t. all vertices are adjacent to eachother (subgraph is a complete graph)

Question 11

Degree Sequence

Answer 11

List of integers from highest to lowest

Question 12

Graphic Sequence

Answer 12

sequence that produces a simple graph

Question 13

Girth

Answer 13

length of shortest cycle

Question 14

Max Edges (simple)

Answer 14

Complete Graph, n choose 2

Question 15

Min Edges (simple connected)

Answer 15

n-1

Question 16

cut-edge/cut-vertex

Answer 16

edge or vertex that if removed increases the number of components (disconnects the graph)

Question 17

subgraph INDUCED by a vertex set S

Answer 17

The graph with only the vertices in S, or G - (complement of S)

Question 18

Spanning Subgraph

Answer 18

Subgraph with vertex set v(G)

Question 19

Forest

Answer 19

A graph with no cycles

Question 20

Tree

Answer 20

A connected graph with no cycles

Question 21

Leaf

Answer 21

vertex with d(v) = 1

Question 22

𝜏(G)

Answer 22

number of spanning trees in G. Can consider all trees containing e then all trees without e separately. 𝜏(G) = 𝜏(G - e) + 𝜏(G · e).

Question 23

Contraction (G · e)

Answer 23

Replace an edge e = uv with a single vertex w, then any edges that were incident with u or v are now incident with w

Question 24

MST

Answer 24

Minimum Spanning Tree, Spanning tree of a weighted graph G with minimum weight.

Question 25

Matching

Answer 25

Independent Set of Edges

Question 26

M-Saturated Vertex

Answer 26

A vertex that is an endpoint of an edge in M

Question 27

Perfect Matching

Answer 27

A matching in which every vertex is saturated

Question 28

Vertex Cover

Answer 28

A set of vertices such that each edge in G has at least one endpoint in the set. *In fact |M| ≤ |Q|. If we have equality then M is maximum and Q is minimum!

Question 29

α’(G)

Answer 29

max size of a matching (independent set of edges)

Question 30

β(G)

Answer 30

min size of a vertex cover

Question 31

α(G)

Answer 31

max size of an independent set of vertices

Question 32

β’(G)

Answer 32

min size of an edge cover (doesn’t exist if their are isolated vertices.. Duh..)

Question 33

K-Factor

Answer 33

A K-regular spanning subgraph

Question 34

Vertex Cut

Answer 34

a set of vertices (S) s.t. G-S is disconnected.

Question 35

Connectivity κ(G)

Answer 35

κ(G) is the minimum size of S s.t. G-S is disconnected or only has 1 vertex

Question 36

k-connected

Answer 36

A graph is k-connected if it can not be disconnected by deleting fewer then k vertices
For all k smaller than or equal to κ(G), G is k connected.

Question 37

κ(G) upper bounds

Answer 37

1. δ(G) (Deleting the neighborhood of the vertex with the smallest degree disconnects the graph)

Question 38

Edge connectivity κ’(G)

Answer 38

Minimum size of F s.t. G-F is disconnected or only has 1 vertex

Question 39

[S, T]

Answer 39

set of edges with one endpoint in S and one endpoint in T where S and T are sets of vertices of G.

Question 40

Edge Cut

Answer 40

[S, S complement]

Question 41

When does k = k’ = δ?

Answer 41

Trees, Cycles, Kn, Km,n hypercube

Question 42

Block

Answer 42

Maximal connected subgraph which has no cut vertex

Question 43

Block-Cut point graph

Answer 43

Bipartite graph with partitions X = {set of blocks} Y = {set of cut vertices} and xy is an edge IFF block x contains cut vertex y. (always a forest)

Question 44

Leaf-Blocks`

Answer 44

A leaves of a block-but point graph (representing blocks)

Question 45

Internally Disjoint Paths

Answer 45

uv paths with no common vertices other than u and v. (will obviously not have any common edges)

Question 46

Subdivison

Answer 46

replacing an edge uv with 2 edges uw and wv with w being a new vertex.

Question 47

Ear

Answer 47

Maximal path all of whose internal vertices have degree 2

Question 48

Ear Decomp

Answer 48

A decomposition of a graph G with a Cycle then all ears.

Question 49

xy separator

Answer 49

Given vertices x,y , a set of vertices S (excluding x,y) is an x,y separator if G-S has no xy path.

Question 50

κ(x,y)

Answer 50

minimum size of an xy separator

Question 51

λ(x,y)

Answer 51

max number of pairwise internally disjoint xy paths

Question 52

xu fan

Answer 52

a set of xu paths whose only common vertex is x.

Question 53

κ’(x,y)

Answer 53

min size of an xy edge separator

Question 54

λ’(x,y)

Answer 54

max number of edge disjoint x,y paths

Question 55

k-coloring

Answer 55

A coloring with at most k color classes is called a k coloring. (called proper if all adjacent vertices have a different color)

Question 56

k-colorable

Answer 56

A graph is k-colorable if there is a proper k-coloring

Question 57

x(G)

Answer 57

Chromatic Number of G, minimum number of colors in a proper coloring

Question 58

ω(G)

Answer 58

clique number - max size of a clique in G

Question 59

x(G) ? ω(G)

Answer 59

≥

Question 60

x(G) ≥ ?

Answer 60

1. ω(G)

2. n(G) / α(G) *each color used at most α times.

Question 61

x(G) ≤ ?

Answer 61

Δ(G) + 1, unless G is connected and not regular`

Question 62

x’(G)

Answer 62

Chromatic Index of G, minimum # of colors in a proper edge coloring

Question 63

x’(G) ≤ ?

Answer 63

1. 3/2 Δ(G)
2. 2Δ(G) - 1
   x’(G) = x(L(G)) ≤ Δ(L(G)) + 1 ≤ 2(Δ(G) - 1) + 1 = 2Δ(G) - 1

Question 64

Line Graph

Answer 64

L(G) is the simple graph with vertex set E(G) and xy is an edge in L(G) IFF x and y share a vertex in G.