 12.3.1: In the argument that Euler gave to solve the Konigsberg Bridge (see...
 12.3.2: Solve the problem dealing with walking through an art exhibit, stat...
 12.3.3: Prove Theorem 12.43: Let G be a connected graph. Then G has an Eule...
 12.3.4: Classify each graph or multigraph in Figure 12.49 as containing (a)...
 12.3.5: Give an example of a graph G of order 6, where (a) G is Eulerian an...
 12.3.6: Prove or disprove the following. (a) Let G be a multigraph with an ...
 12.3.7: Let n 3 be an integer. Prove that Cn is Eulerian if and only if n 5...
 12.3.8: Prove for 1 s t that Ks,t is Eulerian if and only if both s and t a...
 12.3.9: Prove for n 2, that Qn is Eulerian if and only if n is even.
 12.3.10: A graph G of order 8 has the property that G v is Eulerian for ever...
 12.3.11: It is known that every graph of order n 2 contains at least two ver...
 12.3.12: Suppose that G is an Eulerian graph of order n 3 containing exactly...
 12.3.13: Let G be a connected graph of order n 6 that has neither an Euleria...
 12.3.14: Draw K3,4, W5 and P4 + P5.
 12.3.15: Draw the following: (a) P4 + P4. K3 + K3. K2,3 + K2. (b) P4 P4. K3 ...
 12.3.16: Draw Q4.
 12.3.17: What is the order and the size of the ncube Qn?
 12.3.18: For an integer n 2, the vertex set of the graph Rn is the set of n...
 12.3.19: Let G1, G2 and G3 be pairwise disjoint connected regular graphs and...
 12.3.20: Let G be an rregular graph of odd order n and let F = G, where F a...
 12.3.21: Prove or disprove: There exist two connected graphs G and H both of...
 12.3.22: Figure 12.50 shows a map of city divided into six land regions, den...
 12.3.23: Inspector House is investigating the mysterious death of Count Evan...
Solutions for Chapter 12.3: Eulerian Graphs
Full solutions for Discrete Mathematics  1st Edition
ISBN: 9781577667308
Solutions for Chapter 12.3: Eulerian Graphs
Get Full SolutionsDiscrete Mathematics was written by and is associated to the ISBN: 9781577667308. Since 23 problems in chapter 12.3: Eulerian Graphs have been answered, more than 13671 students have viewed full stepbystep solutions from this chapter. This expansive textbook survival guide covers the following chapters and their solutions. This textbook survival guide was created for the textbook: Discrete Mathematics, edition: 1. Chapter 12.3: Eulerian Graphs includes 23 full stepbystep solutions.

Adjacency matrix of a graph.
Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected). Adjacency matrix of a graph. Square matrix with aij = 1 when there is an edge from node i to node j; otherwise aij = O. A = AT when edges go both ways (undirected).

Conjugate Gradient Method.
A sequence of steps (end of Chapter 9) to solve positive definite Ax = b by minimizing !x T Ax  x Tb over growing Krylov subspaces.

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).

Free variable Xi.
Column i has no pivot in elimination. We can give the n  r free variables any values, then Ax = b determines the r pivot variables (if solvable!).

Full row rank r = m.
Independent rows, at least one solution to Ax = b, column space is all of Rm. Full rank means full column rank or full row rank.

Hankel matrix H.
Constant along each antidiagonal; hij depends on i + j.

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.

Left nullspace N (AT).
Nullspace of AT = "left nullspace" of A because y T A = OT.

Linearly dependent VI, ... , Vn.
A combination other than all Ci = 0 gives L Ci Vi = O.

Orthogonal matrix Q.
Square matrix with orthonormal columns, so QT = Ql. Preserves length and angles, IIQxll = IIxll and (QX)T(Qy) = xTy. AlllAI = 1, with orthogonal eigenvectors. Examples: Rotation, reflection, permutation.

Orthonormal vectors q 1 , ... , q n·
Dot products are q T q j = 0 if i =1= j and q T q i = 1. The matrix Q with these orthonormal columns has Q T Q = I. If m = n then Q T = Q 1 and q 1 ' ... , q n is an orthonormal basis for Rn : every v = L (v T q j )q j •

Pivot.
The diagonal entry (first nonzero) at the time when a row is used in elimination.

Plane (or hyperplane) in Rn.
Vectors x with aT x = O. Plane is perpendicular to a =1= O.

Projection p = a(aTblaTa) onto the line through a.
P = aaT laTa has rank l.

Reduced row echelon form R = rref(A).
Pivots = 1; zeros above and below pivots; the r nonzero rows of R give a basis for the row space of A.

Singular Value Decomposition
(SVD) A = U:E VT = (orthogonal) ( diag)( orthogonal) First r columns of U and V are orthonormal bases of C (A) and C (AT), AVi = O'iUi with singular value O'i > O. Last columns are orthonormal bases of nullspaces.

Symmetric matrix A.
The transpose is AT = A, and aU = a ji. AI is also symmetric.

Unitary matrix UH = U T = UI.
Orthonormal columns (complex analog of Q).

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

Vector space V.
Set of vectors such that all combinations cv + d w remain within V. Eight required rules are given in Section 3.1 for scalars c, d and vectors v, w.