 10.1.1: In 1 and 2, graphs are represented by drawings. Define each graph f...
 10.1.2: In 1 and 2, graphs are represented by drawings. Define each graph f...
 10.1.3: In 3 and 4, draw pictures of the specified graphs
 10.1.4: In 3 and 4, draw pictures of the specified graphs
 10.1.5: In 57, show that the two drawings represent the same graph by label...
 10.1.6: In 57, show that the two drawings represent the same graph by label...
 10.1.7: In 57, show that the two drawings represent the same graph by label...
 10.1.8: For each of the graphs in 8 and 9: (i) Find all edges that are inci...
 10.1.9: For each of the graphs in 8 and 9: (i) Find all edges that are inci...
 10.1.10: Use the graph of Example 10.1.6 to determine a. whether Sports Illu...
 10.1.11: Find three other winning sequences of moves for the vegetarians and...
 10.1.12: Another famous puzzle used as an example in the study of artificial...
 10.1.13: Solve the vegetariansandcannibals puzzle for the case where there...
 10.1.14: Two jugs A and B have capacities of 3 quarts and 5 quarts, respecti...
 10.1.15: A graph has vertices of degrees 0, 2, 2, 3, and 9. How many edges d...
 10.1.16: A graph has vertices of degrees 1, 1, 4, 4, and 6. How many edges d...
 10.1.17: In each of 1725, either draw a graph with the specified properties ...
 10.1.18: In each of 1725, either draw a graph with the specified properties ...
 10.1.19: In each of 1725, either draw a graph with the specified properties ...
 10.1.20: In each of 1725, either draw a graph with the specified properties ...
 10.1.21: In each of 1725, either draw a graph with the specified properties ...
 10.1.22: In each of 1725, either draw a graph with the specified properties ...
 10.1.23: In each of 1725, either draw a graph with the specified properties ...
 10.1.24: In each of 1725, either draw a graph with the specified properties ...
 10.1.25: In each of 1725, either draw a graph with the specified properties ...
 10.1.26: Find all subgraphs of each of the following graphs.
 10.1.27: a. In a group of 15 people, is it possible for each person to have ...
 10.1.28: In a group of 25 people, is it possible for each to shake hands wit...
 10.1.29: Is there a simple graph, each of whose vertices has even degree? Ex...
 10.1.30: Suppose that G is a graph with v vertices and e edges and that the ...
 10.1.31: Prove that any sum of an odd number of odd integers is odd
 10.1.32: Deduce from exercise 31 that for any positive integer n, if there i...
 10.1.33: Recall that Kn denotes a complete graph on n vertices. a. Draw K6. ...
 10.1.34: Use the result of exercise 33 to show that the number of edges of a...
 10.1.35: Is there a simple graph with twice as many edges as vertices? Expla...
 10.1.36: Recall that Km,n denotes a complete bipartite graph on (m, n) verti...
 10.1.37: A bipartite graph G is a simple graph whose vertex set can be parti...
 10.1.38: Suppose r and s are any positive integers. Does there exist a graph...
 10.1.39: Find the complement of each of the following graphs.
 10.1.40: a. Find the complement of the graph K4, the complete graph on four ...
 10.1.41: Suppose that in a group of five people A, B,C, D, and E the followi...
 10.1.42: Let G be a simple graph with n vertices. What is the relation betwe...
 10.1.43: Show that at a party with at least two people, there are at least t...
 10.1.44: a. In a simple graph, must every vertex have degree that is less th...
 10.1.45: In a group of two or more people, must there always be at least two...
 10.1.46: Imagine that the diagram shown below is a map with countries labele...
 10.1.47: In this exercise a graph is used to help solve a scheduling problem...
 10.1.48: A department wants to schedule final exams so that no student has m...
Solutions for Chapter 10.1: Graphs: Definitions and Basic Properties
Full solutions for Discrete Mathematics with Applications  4th Edition
ISBN: 9780495391326
Solutions for Chapter 10.1: Graphs: Definitions and Basic Properties
Get Full SolutionsDiscrete Mathematics with Applications was written by Sieva Kozinsky and is associated to the ISBN: 9780495391326. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics with Applications , edition: 4th. Since 48 problems in chapter 10.1: Graphs: Definitions and Basic Properties have been answered, more than 24394 students have viewed full stepbystep solutions from this chapter. Chapter 10.1: Graphs: Definitions and Basic Properties includes 48 full stepbystep solutions.

Complex conjugate
z = a  ib for any complex number z = a + ib. Then zz = Iz12.

Diagonal matrix D.
dij = 0 if i # j. Blockdiagonal: zero outside square blocks Du.

Dot product = Inner product x T y = XI Y 1 + ... + Xn Yn.
Complex dot product is x T Y . Perpendicular vectors have x T y = O. (AB)ij = (row i of A)T(column j of B).

Elimination.
A sequence of row operations that reduces A to an upper triangular U or to the reduced form R = rref(A). Then A = LU with multipliers eO in L, or P A = L U with row exchanges in P, or E A = R with an invertible E.

Ellipse (or ellipsoid) x T Ax = 1.
A must be positive definite; the axes of the ellipse are eigenvectors of A, with lengths 1/.JI. (For IIx II = 1 the vectors y = Ax lie on the ellipse IIA1 yll2 = Y T(AAT)1 Y = 1 displayed by eigshow; axis lengths ad

Exponential eAt = I + At + (At)2 12! + ...
has derivative AeAt; eAt u(O) solves u' = Au.

Fourier matrix F.
Entries Fjk = e21Cijk/n give orthogonal columns FT F = nI. Then y = Fe is the (inverse) Discrete Fourier Transform Y j = L cke21Cijk/n.

Incidence matrix of a directed graph.
The m by n edgenode incidence matrix has a row for each edge (node i to node j), with entries 1 and 1 in columns i and j .

Indefinite matrix.
A symmetric matrix with eigenvalues of both signs (+ and  ).

Kirchhoff's Laws.
Current Law: net current (in minus out) is zero at each node. Voltage Law: Potential differences (voltage drops) add to zero around any closed loop.

Krylov subspace Kj(A, b).
The subspace spanned by b, Ab, ... , AjIb. Numerical methods approximate A I b by x j with residual b  Ax j in this subspace. A good basis for K j requires only multiplication by A at each step.

lAII = l/lAI and IATI = IAI.
The big formula for det(A) has a sum of n! terms, the cofactor formula uses determinants of size n  1, volume of box = I det( A) I.

Left inverse A+.
If A has full column rank n, then A+ = (AT A)I AT has A+ A = In.

Multiplier eij.
The pivot row j is multiplied by eij and subtracted from row i to eliminate the i, j entry: eij = (entry to eliminate) / (jth pivot).

Orthogonal subspaces.
Every v in V is orthogonal to every w in W.

Right inverse A+.
If A has full row rank m, then A+ = AT(AAT)l has AA+ = 1m.

Row space C (AT) = all combinations of rows of A.
Column vectors by convention.

Simplex method for linear programming.
The minimum cost vector x * is found by moving from comer to lower cost comer along the edges of the feasible set (where the constraints Ax = b and x > 0 are satisfied). Minimum cost at a comer!

Toeplitz matrix.
Constant down each diagonal = timeinvariant (shiftinvariant) filter.

Vector addition.
v + w = (VI + WI, ... , Vn + Wn ) = diagonal of parallelogram.