Final

Question 1

A vertex set 𝑉

Answer 1

A collection of points,vertices are dots,

Question 2

An edge set 𝐸

Answer 2

A collection of unordered pairs of vertices representing connections between them
edges are lines connecting these dots.

Question 3

A walk from vertex
𝑣1To 𝑣𝑛
​

Answer 3

is a sequence of edges

{V1,V2}{V2,V3},…{Vn-1,Vn}

Question 4

A circuit is a walk where the start and end vertices are the same:

Answer 4

A circuit is a walk where the start and end vertices are the same:

V1=Vn

Question 5

A path

Answer 5

is a walk in which no vertex is revisited

Vi/=Vj for all i and j

Question 6

Cycle:

Answer 6

A cycle is a special type of circuit with these properties:
It starts and ends at the same vertex (𝑣
1
=
𝑣
𝑛
v
1
​
=v
n).

Question 7

A walk vs A path

Answer 7

A walk may revisit vertices and edges, while a path cannot revisit vertices.

Question 8

A circuit and a cycle

Answer 8

A circuit revisits the starting vertex and has a direction, while a cycle is undirected and only revisits the start/end vertex.

Question 9

A path from x to y is a walk in G that has no repeated veritices

Answer 9

A path from x to y is a walk in G that has no repeated veritices

Question 10

A trail from x to y is an open walk in G in which each edge appears no more than it multiplicity

Answer 10

A trail from x to y is an open walk in G in which each edge appears no more than it multiplicity

Question 11

A circuit from x to x is a closed walk in G in which each edge appears no more than its multiplicity

Answer 11

A circuit from x to x is a closed walk in G in which each edge appears no more than its multiplicity

Question 12

Euler Trail

Answer 12

Visit every edge exactly one, doesn’t necessarily start and end at the same vertex

The graph must be connected
Has exactly 2 vertices must have an odd degree

Question 13

Euler circuit

Answer 13

Visit every edge once
Starts and ends at the same vertex
Graphs must be connected
Vertices have an even degree

Question 14

Let G(V, E) be a multi-graph

Answer 14

G is a tree if G is connected and does not contain a cycle
G is a forest if G does not contain a cycle (every component of a forest is a tree)
A vertex of deg 1 is called a leaf or pendant vertex

Question 15

If T=(V, E) is a tree with leaf v the T-v is a tree

Answer 15

If T=(V, E) is a tree with leaf v the T-v is a tree

Question 16

If T=(V, E) is a tree and u, v∈ V are distinct, there is a unique path in T with ends u,v

Answer 16

If T=(V, E) is a tree and u, v∈ V are distinct, there is a unique path in T with ends u,v

Question 17

Main properties of tree

Answer 17

If T= (V, E) is a tree the |V|=|E|+1
If G=(V,E) is a forest with K trees then |V|=|E|+K

Question 18

If G=(V, E) satisfies|V|=|E|+1 then G must have a vertex of deg 0 or at least two degrees of 1

Answer 18

If G=(V, E) satisfies|V|=|E|+1 then G must have a vertex of deg 0 or at least two degrees of 1

Question 19

Every tree T=(V, E) with |V|>2 has at least 2 leaves

Answer 19

Every tree T=(V, E) with |V|>2 has at least 2 leaves

Question 20

Deg sum formla

Answer 20

Σdeg(V)=2.|E|

Question 21

Characterization of trees

let G=(V, E) be a multigraph

Answer 21

1. G is connected and has no cycle
2. G is connected and |V|=|E|+1
3. G has no cycle and |V|=|E|+1
4. There is a unique path between every pair of vertices in G

Question 22

Bipartite graph

Answer 22

if we can partition the vertices into 2 non-empty subset V1 and V2 such that

1) V1^V2=DNE
2) V1vV2=v
3) every edge in E is incident with one vertex in V1 and one vertex in V2

Question 23

Km,n

|V1|=n and |V2|=m

Answer 23

of edges = n.m

Question 24

How many edges are in a path on n vertices

Answer 24

n-1

Question 25

How many edges are in a cycle on n vertices

Answer 25

n

Question 26

How many edges are in Kn?

Answer 26

nC2

Question 27

How many edges are in Km,n?

Answer 27

n.m

Question 28

How many graphs are there with vertices {1,…n}?

Answer 28

We can choose from nC2 edges—->

Question 29

How many graphs have n vertices and m edges?

Answer 29

(nC2)Cm

Question 30

Let V1 and V2 be disjoint with |V1|=n1 and |V2|=n2

how many graphs have bipartition (V1, V2)?

Answer 30

2^(n1.n2)

Question 31

Let V1 and V2 be disjoint with |V1|=n1 and |V2|=n2

how many graphs have bipartition (V1, V2) with m edges?

Answer 31

(n1.n2) C m

Question 32

How many spanning subgraphs do Kn1, n2 have?

Answer 32

2^(n1.n2)

Question 33

How many spanning subgraphs do Kn1,n2 have exactly m edges?

Answer 33

(n1.n2) C m

Question 34

induced subgraph

Answer 34

Question 35

If G=(V, E) is a graph with |V|=n, how many induced subgraphs does G have?

Answer 35

Guess 2^n, correct!

An induced subgraph is determined by the vertex V’cC and 2 different V’ give different subgraphs.

of subsets V’ is a subset of V is indeed 2^n