Simple graphs are defined as digraphs in which edges are undirected.
2 Handshaking Lemma
The sum of the degrees of the vertices in a graph equals twice the number of edges.
3 Some Common Graphs
A complete graph Kn has n vertices and an edge between every two vertices, for a total of n(n-1)/2 edges.An n-node graph containing n-1 edges in sequence is known as a line graph Ln.If we add the edge < vn — v1 > to the line graph Ln, we get a graph called a lengthn cycle Cn.
4 Isomorphism
two graphs are isomorphic when there is an edge-PReserving matching of their vertices.isomorphism is an equivalence relation.If some property preserved by isomorphism differs for two graphs, then they’re not isomorphic: # of nodes,# of edges,degree distributions, ….
