3033: CHAPTER 1: BASIC NOTIONS

Question 1

Definition of a graph

Answer 1

A graph is a pair of sets G=(V,E) such that E ⊆ V^{2}

Question 2

What is A^{2}?

Answer 2

The set of 2 element subsets of A

Question 3

What is the maximum number of vertices for a graph of n vertices?

Answer 3

(n 2) = n!/2!*(n-2)!

Question 4

For 2<=k

Answer 4

It is the graph whose vertices are the k-element subsets of {1,…,n} with two k-subsets adjacent if they intersect in a (k-1)-subset

Question 5

What does it mean for 2 vertices to be adjacent?

Answer 5

There is an edge between them

Question 6

When are two vertices u and v neighbours?

Answer 6

When there is an edge between them

Question 7

What does it mean for a vertex v to be incident to an edge e?

Answer 7

The edge e has an endpoint at v

Question 8

What is the d(v)?

Answer 8

The number of edges incident to v

Question 9

When is a vertex isolated?

Answer 9

When it has degree 0

Question 10

What is the handshaking lemma?

Answer 10

SUM (i=1 n)(d(xi)) = 2|E|

Question 11

For a graph G=(V,E), what is a subgraph?

Answer 11

A graph G’=(V’,E’) where V′⊆V and E′⊆E.

Question 12

When is a subgraph a spanning subgraph?

Answer 12

When V’=V

Question 13

When is a subgraph an induced subgraph?

Answer 13

When for all u,v ∈ V′, if uv ∈ E then uv ∈ E′.

Question 14

When is a graph G complete?

Answer 14

When there is an edge between any two vertices

Question 15

When is a graph G null?

Answer 15

When it has no edges

Question 16

Let G = (V,E) be a graph. What is a bipartition of G?

Answer 16

It is a pair of subsets X,Y ⊆ V such that X ∪ Y = V, X ∩ Y =∅ and every edge of G has one endpoint in X and the other in Y

Question 17

When is G complete bipartite

Answer 17

If it has a bipartition X , Y such that every vertex in X is adjacent to every vertex in Y .

Question 18

Let G be a graph. For k ∈ N, what does it for G to be k-regular?

Answer 18

All the vertices of G have degree k.

Question 19

Let G = (V,E) be a graph. For a subset V′ ⊆ V, what is G −V′?

Answer 19

It is the graph obtained from G by deleting the vertices in V ′ and deleting all edges incident with them

Question 20

Let G = (V,E) be a graph. For a subset E′ ⊆ E, what is G−E′?

Answer 20

It is the graph obtained from G by deleting the edges in E′?

Question 21

Let G = (V , E ) be a graph. What is the complement of G?

Answer 21

It is the graph Gc = (Vc, Ec), where Vc =V and Ec = V^{2}\E

Question 22

Let G = (V,E) and G′ = (V′,E′) be graphs. What is an isomorphism f : G → G′ ?

Answer 22

It is a bijective function f : V → V′ such that u and v are adjacent in G if and only if f(u) and f(v) are adjacent in G ′ , for all u , v ∈ V .

Question 23

If G ∼= H then what can we say about Gc and Hc

Answer 23

Gc ∼= Hc.

Question 24

What is an automorphism?

Answer 24

It is an isomorphism of a graph G to itself

Question 25

Let G = (V , E ) be a graph. When is G vertex-transitive

Answer 25

When if for any u, v ∈ V, there is an automorphism α: G → G with α(u) = v.

Question 26

If G is vertex-transitive graph. Then what can we say about it?

Answer 26

(i) G is regular
(ii) the complement Gc of G is also vertex-transitive

Question 27

What is an edge sequence of G?

Answer 27

It is a sequence of vertices
v0 v1 … vk
such that v0v1,v1v2,…vk−1vk ∈ E.

Question 28

What is a path?

Answer 28

It is an edge sequence where all the vertices in it, except possibly its initial and final vertex, are distinct.

Question 29

Let G = (V,E) be a graph. For u,v ∈ V, what is d(u,v)?

Answer 29

It is the length of the shortest path from u to v

Question 30

If there is no path between u and v what is d(u,v)?

Answer 30

∞

Question 31

What is the diameter of G?

Answer 31

max{d(u,v) | u,v ∈ V}

Question 32

Let G = (V,E) be a graph and u,v ∈ V. Then what can we say about uv-edge sequences and uv-paths?

Answer 32

Every uv-edge sequence contains a uv-path

Question 33

What does it mean for an edge sequence to be closed?

Answer 33

It’s initial and final vertex are the same

Question 34

What is a cycle?

Answer 34

A closed path

Question 35

What is the birth of G?

Answer 35

The length of the shortest cycle in G

Question 36

What does it mean for G to be connected?

Answer 36

If for any two vertices u, v of G there is a path from u to v.

Question 37

Let G = (V,E) be a graph. When is an edge e ∈ E a bridge?

Answer 37

if removing e from G disconnects the graph, i.e. G − e is disconnected

Question 38

What is a connected component of G

Answer 38

It is a maximal connected subgraph of G

Question 39

Let G = (V , E ) be a graph with n vertices and k edges. What can we say if G connected

Answer 39

k ≥ n − 1

Question 40

What is a forest?

Answer 40

A graph with no cycles

Question 41

What is a tree?

Answer 41

A connected graph with no cycles

Question 42

Given a tree T, what is a leaf?

Answer 42

A vertex of degree 1

Question 43

What can we say about a tree with n ≥ 2 vertices.

Answer 43

i) G has at least two leaves.
(ii) If v is a leaf, then G −v is a tree with n−1 vertices.

Question 44

Let G be a graph with n ≥ 1 vertices. Then the following conditions are equivalent to G being a tree?

Answer 44

(ii) G has no cycles and has n − 1 edges.
(iii) G is connected and has n − 1 edges.
(iv) G is connected, and every edge is a bridge.
(v) each pair of vertices in G is connected by a unique path.
(vi) G has no cycles, but adding any one edge creates a cycle.

Question 45

Let G = (V,E) be a graph. When is G an Eulerian graph?

Answer 45

If G has an Eulerian tour, i.e. a closed edge sequence that contains every edge of G exactly once.

Question 46

If every vertex of a graph has degree of at least 2, what can we say about it?

Answer 46

G has a cycle

Question 47

Let G be a connected graph. When is G Eulerian?

Answer 47

Iff every vertex has even degree