Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.



Graphs
Posted:
Jun 30, 2006 7:18 PM


Is this the place to ask about graph theory for beginners? I am trying to learn some elementary theory from "Introduction to Graph Theory" by Richard J. Trudeau and "A Beginner's Guide to Graph Theory" by W. D. Wallis. I have some questions from the early chapters. Specifically, from the definition of an adjacency matrix, I would expect the main diagonal, i.e., m 1,1, m 2,2, ..., m v,v, to consist of all zeros, and the matrix to have bilateral symmetry about this diagonal. However, this is not the case in the example given by Wallace (p.6). What am I missing? Another specific, which Trudeau gives as an exercise (p.59): "...If we ignore...v1...that leaves v=4 as the only number of vertices listed [through v=9] for which there are an odd number of graphs. Do you think this is due to chance, or can you think of some reason why v=4 should be unique?..." Although I see why the number of graphs is even for v=2 mod 4 or for v=3 mod 4, I can think of no reason why there cannot be an odd number of graphs for some v=0 mod 4 or v=1 mod 4, other than v=4. Is there a reason? If so, what is it? Are there other values of v for which there are an odd number of graphs? Thanks for any help, or suggestions for further reading at an elementary level. Mary Krimmel



