Discrete Mathematics

A simple graph can have
(i) multiple edges
(ii) self-loops
(iii) parallel edges
(iv) no multiple edges, self-loops and parallel edges

An undirected graph has 8 vertices labelled $1, 2, \dots, 8$ and 31 edges. Vertices $1, 3, 5, 7$ have degree 8 and vertices $2, 4, 6, 8$ have degree 7. What is the degree of vertex 8?

(i) 15
(ii) 8
(iii) 5
(iv) 23

A graph which has the same number of edges as its complement must have number of vertices congruent to ______ or ______ modulo 4 (for integral values of number of edges).

(i) $6k, 6k-1$
(ii) $4k, 4k+1$
(iii) $k, k+2$
(iv) $2k+1, k$

A graph which consists of disjoint union of trees is called
(i) bipartite graph
(ii) forest
(iii) caterpillar tree
(iv) labelled tree

If $C_n$ is the $n$th cyclic graph, where $n>3$ and $n$ is odd, determine the value of $\chi(C_n)$.

(i) 32572
(ii) 16631
(iii) 3
(iv) 310

The number of edges in a regular graph of degree 46 and 8 vertices is

(i) 347
(ii) 230
(iii) 184
(iv) 186

In a Round-Robin tournament, the Tigers beat the Blue Jays, the Tigers beat the Cardinals, the Tigers beat the Orioles, the Blue Jays beat the Cardinals, the Blue Jays beat the Orioles and the Cardinals beat the Orioles. Model this outcome with a directed graph.

Determine whether the following given pair of directed graphs, shown in Fig. 1 and Fig. 2, are isomorphic or not. Exhibit an isomorphism or provide a rigorous argument that none exists.

Consider the following graph

(a) Does a Hamiltonian path exist? If so describe it. If not say why not.

Use pseudocode to describe an algorithm for determining the value of a game tree when both players follow a minimax strategy.

Does an Eulerian path exist? If so describe it. If not say why not.

Suppose that $T_1$ and $T_2$ are spanning trees of a simple graph $G$. Moreover, suppose that $e_1$ is an edge in $T_1$ that is not in $T_2$. Show that there is an edge $e_2$ in $T_2$ that is not in $T_1$ such that $T_1$ remains a spanning tree if $e_1$ is removed from it and $e_2$ is added to it, and $T_2$ remains a spanning tree if $e_2$ is removed from it and $e_1$ is added to it.

Show that a degree-constrained spanning tree of a simple graph in which each vertex has degree not exceeding 2 consists of a single Hamiltonian path in the graph.