91Ó°ÊÓ

Refer to the adjacency matrix \(A\) of \(K_{5}\). Let \(d_{n}\) be the common value of the diagonal elements of \(A^{n}\) and let \(a_{n}\) be the common value of the off-diagonal elements of \(A^{n}\). Show that $$d_{n+1}=4 a_{n} ; \quad a_{n+1}=d_{n}+3 a_{n} ; \quad a_{n+1}=3 a_{n}+4 a_{n-1}$$

Paul Erd?s \((1913-1996)\) was one of the most prolific mathematicians of all time. He was the author or co-author of nearly 1500 papers. Mathematicians who co-authored a paper with Erd?s are said to have Erd?s number one. Mathematicians who did not co-author a paper with Erd?s but who co-authored a paper with a mathematician whose Erd?s number is one are said to have Erdós number two. Higher Erd?s numbers are defined similarly. For example, the author of this book has Erd?s number five. Johnsonbaugh co-authored a paper with Tadao Murata, Murata co-authored a paper with A. T. Amin, Amin co- authored a paper with Peter J. Slater, Slater co-authored a paper with Frank Harary, and Harary co-authored a paper with Erdõs. Develop a graph model for Erd?s numbers. In your model, what is an Erd?s number?

Draw all nonisomorphic simple graphs having four vertices.

Draw all nonisomorphic, cycle-free, connected graphs having six vertices.

When does the complete graph \(K_{n}\) contain an Euler cycle?

When does the complete bipartite graph \(K_{m, n}\) contain an Euler cycle?

For which values of \(n\) does the \(n\) -cube contain an Euler cycle?

How many edges are incident on a vertex in an \(n\) -cube?

How many edges are in an \(n\) -cube?

The complement of a simple graph \(G\) is the simple graph \(\bar{G}\) with the same vertices as \(G .\) An edge exists in \(\bar{G}\) if and only if it does not exist in \(G\). Given two graphs \(G_{1}\) and \(G_{2},\) suppose that there is a one-toone, onto function \(f\) from the vertices of \(G_{1}\) to the vertices of \(G_{2}\) and a one-to-one, onto function \(g\) from the edges of \(G_{1}\) to the edges of \(G_{2},\) so that if an edge \(e\) is incident on \(v\) and \(w\) in \(G_{1},\) the edge \(g(e)\) is incident on \(f(v)\) and \(f(w)\) in \(G_{2} .\) Are \(G_{1}\) and \(G_{2}\) isomorphic?