Discrete Mathematics 1st Edition solutions

Discrete Mathematics 1
Let V = {P(n),Q(n),R(n)} be the set of the following open sentences involving integers n: P(n): n is even. Q(n): 4n + 1 is even. R(n): n2 is even. Draw a digraph D with vertex set V , where for A,B V , there is a directed edge from A to B if n Z,A B is a true statement.

Discrete Mathematics 1
Let S = {3, 6, 9, 18}. (a) The vertex set of a graph G is S and two vertices i and j are adjacent if either i | j or j | i. Draw the graph G. (b) The vertex set of a digraph D is S and (i, j) is an arc of D if i | j. Draw the digraph D. (c) What can you say about the graph G in (a) and the digraph D

Discrete Mathematics 1
(a) The vertex set of a digraph D is V (D) = {M1,M2,M3,M4}, where M1,M2,M3 and M4 are the four 2 2 matrices M1 = _ 0 1 0 0 _, M2 = _ 0 0 1 0 _, M3 = _ 1 1 0 0 _ and M4 = _ 0 0 1 1 _. There is a directed edge from the vertex Mi to the vertex Mj (i 6= j) if MiMj = _ 0 0 0 0 _. Draw the digraph D. (b)

Discrete Mathematics 1
A digraph D contains three vertices with indegree 0 and three vertices with indegree 2. The remaining two vertices of D have indegree 1. One of these eight vertices has outdegree 0 and another has outdegree 2. The remaining vertices have the same outdegree. What is this outdegree? Draw a digraph havi

Discrete Mathematics 1
Let D be a digraph obtained by assigning a direction to each edge of the cycle Cn of order n 3. Prove that D either contains an even number of vertices having indegree 0 or an even number of vertices having outdegree 0.

Discrete Mathematics 1
Determine the adjacency matrix for each digraph in Figure 15.11.

Discrete Mathematics 1
(a) Prove that if a connected digraph D is strong, then od v > 0 and id v > 0 for every vertex v of D. (b) Is the converse of (a) true?

Discrete Mathematics 1
Use the technique employed in the proof of Theorem 15.5 to construct a strong orientation of the graph G of Figure 15.12.

Discrete Mathematics 1
Determine all (non-isomorphic) orientations of the 5-cycle C5.

Discrete Mathematics 1
Determine the number of orientations of the star K1,t (t 1).

Discrete Mathematics 1
Determine the number of orientations of the graph G in Figure 15.13.

Discrete Mathematics 1
Let G be a connected graph of order n 3. Prove that there is an orientation of G in which no directed path has length 2 if and only if G is bipartite.

Discrete Mathematics 1
The converse ~D of a digraph D is obtained from D by reversing the direction of every arc of D. Show that a digraph D is strong if and only if its converse ~D is strong.

Discrete Mathematics 1
(a) Does there exist a digraph D of order n 3 in which no two vertices of D have the same outdegree but every two vertices of D have the same indegree? (b) Does there exist a digraph D of order n 3 such that no two vertices of D have the same indegree and no two vertices of D have the same outdegre

Discrete Mathematics 1
A digraph D is Eulerian if D contains a directed circuit that contains every directed edge of D. Let D be a connected digraph of order n 3 with V (D) = {v1, v2, , vn}. Prove the following. (a) The digraph D is Eulerian if and only if od vi = id vi for 1 i n. (b) If od vi id vi for 1 i n, the

Discrete Mathematics 1
Prove that a graph G has an Eulerian orientation (see Exercise 15) if and only if G is Eulerian.

Discrete Mathematics 1
According to Theorem 15.5 a nontrivial graph G has a strong orientation if and only if G is connected and contains no bridges. (a) Prove that if G is a nontrivial connected graph with at most two bridges, then there exists an orientation D of G having the property that if u and v are any two vertices

Discrete Mathematics 1
Does there exist a strong orientation D of a graph G and two vertices u and v of G such that ~dD(u, v) 6= dG(u, v) and ~dD(v, u) 6= dG(v, u)?

Discrete Mathematics 1
Prove that if every vertex of a digraph D has positive outdegree, then D contains a directed cycle.

Discrete Mathematics 1
Let G be a nontrivial connected graph without bridges. (a) Show that for every edge e of G and for every orientation of e, there exists an orientation of the remaining edges of G such that the resulting digraph is strong. (b) Show that (a) need not be true if we begin with an orientation of two edges

Discrete Mathematics 1
Let D be a digraph with V (D) = {1, 3, 5, 9, 11, 13} and let A = {2, 8} and B = {4, 10}. A vertex i is adjacent to a vertex j in D if j i A and j is adjacent to i if j i B. Is D strong?

Discrete Mathematics 1
(a) Two people A and B play a game on the complete graph K4. These two people alternate assigning a direction to an edge, beginning with A. It is the goal of A is to produce a strong orientation of K4 while it is the goal of B to stop A from doing this. If both players play perfectly, who will win th

Discrete Mathematics 1
Let T be a nontrivial tree and let r and s be two distinct vertices of T . Let D be the digraph with V (D) = V (T ) such that (u, v) is a directed edge of D if the r v path in T contains u or the s v path in T contains u. (Thus D may contain both (u, v) and (v, u)). What is the strong subdigraph of