Discrete Definitons

Question 1

Given a graph G(V, E), define a walk in a graph

Answer 1

A sequence of edges (e1, e2,…,eL) is a walk if there exists a corresponding sequence of vertices (v0, v1,…,vL) such that ej = (vj-1, vj ). Note that the vertices don’t have to be distinct. If v0 = vL, it is a closed walk

Question 2

Given a graph G(V, E), define a trail in a graph

Answer 2

A trail is a walk in which all the edges ej are distinct

Question 3

Given a graph G(V, E), define a path in a graph

Answer 3

A path is a trail in which all the vertices are distinct

Question 4

Given a graph G(V, E), what is meant by saying G is a connected graph?

Answer 4

Two vertices are said to be connected if there is a walk between them, and a graph in which each pair of vertices is connected is a connected graph.

Question 5

Given a graph G(V, E), what is meant by the degree of a vertex v?

Answer 5

The degree of a vertex v is the number of edges that include the vertex

Question 6

Explain what is meant by the degree sequence of a graph

Answer 6

The degree sequence of graph is a list of the degrees of the vertices, arranged in ascending order.

Question 7

Explain what is meant by saying a graph is a tree

Answer 7

A tree is a connected, acyclic graph

Question 8

Explain what is meant by saying a vertex v in a graph is a leaf

Answer 8

A vertex v in a tree is called a leaf if deg(v)=1

Question 9

Explain what is meant by saying two graphs G1(V1,E1) and G2(V2,E2) are isomorphic

Answer 9

Two graphs G1(V1, E1) and G2(V2, E2) are said to be isomorphic if there exists a bijection α : V1 → V2 such that the edge (α(a), α(b)) ∈ E2 iff (a, b) ∈ E1.

Question 10

Explain what is meant by saying a graph is bipartite

Answer 10

A graph G(V,E) is said to be a bipartite graph if
• it has a non empty edge set E ≠ ∅; and
• its vertex set V can be decomposed into two non empty, disjoint subsets
V = V1 U V2 with V1 ∩ V2 = ∅; and V1 ≠ ∅ ; and V2 ≠ ∅ ;
in such a way that all the edges in E connect a member of V1 with a member of V2

(u, v) ∈ E ⇒{ u ∈ V1 and v ∈ V2
{ or u ∈ V2 and v ∈ V1.

Question 11

What is a k colouring of a graph G?

Answer 11

A k-colouring of G is a function Φ : V → {1,…,k} that assigns distinct values (called colours) to adjacent vertices

Question 12

What is the chromatic number, χ(G), of G?

Answer 12

The chromatic number χ(G) is the smallest number k such that G is k-colourable

Question 13

What is the adjacency matrix of a graph G?

Answer 13

First numbering the vertices, so that the vertex set becomes V = {1, 2,…,n} for a graph on n vertices. The adjacency matrix A is an nxn matrix whose entries are given by:
Aij = {1 if (i, j) ∈ E
{0 otherwise

Question 14

Given a connected graph G(V, E) explain what is meant by saying G is Hamiltonian?

Answer 14

A graph that contains a Hamiltonian tour (a cycle that contains every vertex) is said to be a Hamiltonian graph

Question 15

Given a connected graph G(V, E) explain what is meant by saying G has an Eulerian Tour?

Answer 15

An Eulerian tour in a multigraph G(V,E) is a trail that includes each of the graph’s edges exactly once and starts and finishes at the same vertex.

Question 16

Given a connected graph G(V, E) explain what is meant by saying G is planar?

Answer 16

A graph G is said to be planar if it is possible to draw it in such a way that the edges intersect only at their vertices

Question 17

Given a connected graph G(V, E) explain what is meant by saying G has girth g?

Answer 17

If a graph G(V, E) contains one or more cycles then the girth of G is the length of a shortest cycle.

Question 18

What is meant by saying a graph is acyclic?

Answer 18

A graph is acyclic if it doesn’t include any cycles

Question 19

Explain what is meant by saying 2 vertices in a directed graph are strongly connected

Answer 19

Two vertices a and b in a directed graph are strongly connected if b is accessible from a and a is accessible from b. Additionally, we regard a vertex as strongly connected to itself.

Question 20

Explain what is meant by a relation ~ on a vertex set V is an equivalence relation

Answer 20

A relation ~ on a set S is an equivalence relation if it is:

reflexive: a ~ a for all a ∈ S;
symmetric: a ~ b ⇒ b ~ a for all a, b ∈ S;
transitive: a ~ b and b ~ c ⇒ a ~ c for all a, b, c ∈ S.

Question 21

What does it mean for two graphs to be homeomorphic?

Answer 21

Two graphs G(V, E) and G’(V’, E’) are said to be homeomorphic if they are isomorphic to subdivisions of the same graph.

Question 22

What is a spanning tree in an undirected graph G(V,E)?

Answer 22

A subgraph of G(V,E) is a spanning tree if it is a tree that contains every vertex in V

Question 23

What is a spanning arborescence rooted at v in a digraph G(V,E)?

Answer 23

A subgraph T(V,E’) of a digraph G(V,E) is a spanning arborescence if T is an arborescence that contains all the vertices of G.

Question 24

What is a a single predecessor graph (spreg) rooted at v in a digraph G(V,E)?

Answer 24

A spreg with distinguished vertex v is a directed graph G(V,E) in which each vertex other than the distinguished
vertex v has exactly one predecessor while v itself has no predecessors

Question 25

Explain what it means for a graph G(V,E) to have a planar diagram

Answer 25

If the graph is planar, the way it can be drawn such that the edges intersect only at their vertices is called a planar diagram

Question 26

Explain what it means for a graph H(V’, E’) to be a subdivision of another graph G(V,E)

Answer 26

A subdivision of a graph G(V, E) is a graph H(V, E0) formed by (perhaps repeatedly) removing an edge e = (a, b) ∈ E from G and replacing it with a path {(a, v1), (v1, v2), . . . ,(vk, b)}
containing of some number k > 0 of new vertices {v1, . . . , vk}, each of which has degree 2

Question 27

How many spots has Faz got?

Answer 27

∞

Question 28

Define a forest

Answer 28

A forest is a graph whose connected components are trees

Question 29

Given a connected graph G(V, E) explain what is meant by saying G is Eulerian

Answer 29

A multigraph that contains an Eulerian tour is said to be an Eulerian multigraph.

Question 30

Explain what is meant by a cyclic graph

Answer 30

A cyclic graph is a graph containing at least one cycle

Question 31

What’s greasier? Jim’s hair or a chip shops deep fat fryer?

Answer 31

Jim’s hair

Question 32

A graph G(V,E) is a directed tree or arborescence if?

Answer 32

(i) G contains a root
(ii) The graph |G| that one obtains by ignoring the directedness of the edges is a
tree

Question 33

In a directed graph G(V,E) a vertex b is said to be accessible if?

Answer 33

vertex a if G contains a walk from a to b. Additionally,

we’ll say that all vertices are accessible (or reachable) from themselves.

Question 34

What is a root you mugs

Answer 34

A vertex v in a directed graph G(V,E) is a root if every other
vertex is accessible from v.