1.3 Vertex degrees and counting Degree sequences and graphic sequences. d1 >= ... >= dn is a degree sequence of some graph if and only if their sum is even. A graphic sequence is a degree sequence of a simple graph, for which we saw an algorithmic test. 2-switches maintain the degree sequence of a graph 1.4 Digraphs The underlying graph is the undirected version Weakly connected versus strongly connected Vertex indegrees and outdegrees sum of indegrees = sum of outdegrees Eulerian digraphs A digraph is Eulerian if and only if indegree=outdegree at every node. Application to de Bruijn cycles. Tournaments are orientations of the clique 2.1 Trees and distance Forest, tree, leaf, spanning tree Four equivalent definitions of a tree Given two spanning trees T and T' there are two theorems about taking an edge from one to replace an edge in the other and get another spanning tree. Distance, diameter, eccentricity, radius, center 2.2 Spanning trees and Enumeration (1st section only) Cayley's formula: there are n^(n-2) labeled trees on n vertices Proof using Prufer codes 2.3 Optimization and Trees Kruskal's algorithm for minimum spanning tree Dijkstra's algorithm for single-source shortest paths