Final

Question 1

Graph

Answer 1

A graph is a pair G = (V; E) where V is a finnite set and E is a set of two-element subsets
of V .

Question 2

Adjacent

Answer 2

: Suppose G = (V; E) is a graph and (u,v) a member of V . Then, u is adjacent to v if uv is an edge in
G. This is denoted: u (tilda) v.

Question 3

Degree

Answer 3

Let G = (V; E) be a graph and let v be a member of V . The degree of v is the number of edges with
which v is incident. We denote this: dG(v) or simply d(v) (when there is no confusion about the
graph in question).

Question 4

Max/Min degree of G

Answer 4

The maximum degree of a vertex in G is denoted (triangle) (G). The
minimum degree of a vertex in G is denoted (small delta)(G).

Question 5

regular graph

Answer 5

Regular graphs: If all vertices in G have the same degree, we call G regular

Question 6

The sum of the degrees of the vertices of G

Answer 6

is twice the number of edges

Question 7

Subgraph

Answer 7

Let G,H be graphs. H is a subgraph of G if V(H) is a subset of V(G) and E(H) is a subset of V(G)

Question 8

Spanning subgraph

Answer 8

a sub graph with verts equal to those of the original graph

Question 9

Induced Subgraph

Answer 9

, an induced subgraph (induced by a subset A of the vertices) includes the edges of
H with endpoints that are both vertices in A (and only those edges).

Question 10

Clique

Answer 10

A subset of vertices is a clique provided any two distinct vertices in the subset are adjacent. The “clique number” of G is the size of the largest clique; it is denoted (weird w)(G)

Question 11

independent sets

Answer 11

subset of vertices where no two vertices are adjacent. denoted alpha(G)

Question 12

complement

Answer 12

the complement of G has the same vertices as G but has every edge that G does not
have (and no more).

Question 13

A subset V (G) is a clique of G if and only if

Answer 13

it is an independent set of the complement of G

Question 14

Let G be a graph with at least six vertices. Then

Answer 14

Then (weird w)(G)>= 3 or (weird w)(Gcompliment) >=3

Question 15

Walk

Answer 15

let G={V,E} be a graph. A walk in G is a sequence of Verticies with each vertex adjacent to the next that is W=(vo,v1,….,vt) with all adjacent

Question 16

Path

Answer 16

a path in a graph is a walk with no repeated verticies

Question 17

Component

Answer 17

a component of G is a subgraph of G induced on an equivalence class of the is-connected-to relation on V(g)

Question 18

connected

Answer 18

a graph is called connected provided each pair of vertices in the graph are connected by a path.

Question 19

Cut Vertex/Cut Edge

Answer 19

cut vertex of G provided G-v has more compnenets than G. Cut edge off G provided G-e has more cmponents than G

Question 20

If there is an (x,y)-walk in G

Answer 20

then there is an (x,y)-path in G

Question 21

Let G be a graph, the is-connected to relation is

Answer 21

an equivalence relation on V(g)

Question 22

Let G be a connected graph and suppose e in E(g) is a cut edge of G. Then

Answer 22

G-e has exactly two components`

Question 23

Cycle

Answer 23

a cycle is a walk of at least three in which the first and last vertex are the same with no other repeated vertices. A cycle also refers to the graph or sub graph consisting of the vertices and edges of such a walk. A cycle on n vertices is denoted Cn.

Question 24

Forest

Answer 24

Let G be a graph, if G contains no cycles, then G is acyclic. Alternatively, we call G a forest

Question 25

Tree

Answer 25

a connected, acyclic graph

Question 26

Leaf

Answer 26

a leaf of a graph is a vertex of degree 1

Question 27

Spanning tree

Answer 27

Let G be a graph. A spanning tree of G is spanning subgraph of G that is a tree

Question 28

5 ways to say G is a treee

Answer 28

G is a tree
G is connected and acyclic
G is connected and every edge of G is a cut edge
Between any two vertices of G there is a unique path
G is connected and size of E(G)= size of V(G)-1

Question 29

A graph has a spanning tree iff

Answer 29

it is connected

Question 30

k coloring

Answer 30

the function f:V(G)–>{1,2,3,…k}

Question 31

we call a coloring proper provided that

Answer 31

for all xy in the edges of G. f(x)!=f(y)

Question 32

if a graph has a proper k-coloring

Answer 32

we call it k colorable

Question 33

Chromatic Number

Answer 33

Let G be a graph, the smallest positive integer K for which G is k-colorable is called the chromatic number of G. The chromatic number of G is denoted (chi)(g)

Question 34

Bipartite

Answer 34

a graph G is called bipartite provided it is 2-colorable

Question 35

complete bipartite graphs

Answer 35

Kn,m is a graph whose vertices can be partitioned V=XuY st.

i. size(X)=n
ii. size(Y)=m
iii. for all x in X and for all y in Y, xy is an edge
iv. no edge has both its endpoints in X or both its endpoints in Y

Question 36

Let G be a graph with maximum degree BIG DELTA then (chi)(G)

Answer 36

<=(big delta)+1

Question 37

trees are bipartite

Answer 37

true

Question 38

a graph is bipartite iff

Answer 38

it does not contain an odd cycle

Question 39

of distinct trees with vertex set {1,2,3…,n}

Answer 39

is n^(n-2)

Question 40

Pascals Identity

Answer 40

n choose k = (n-1 choose k-1)(n-1 choose k)