6.042J Lecture Notes - Lecture 10: Handshaking Lemma, Complete Graph, If And Only If

• School: MIT
• Department: Electrical Engineering and Computer Science
• Course: 6.042J
• Professor: Albert Meyer

Document Summary

Simple graphs model relationships that are symmetric, meaning that the relationship is mutual. Examples: marriage, speaking the same language, being connected by a conducting wire. Simple graphs are de ned as digraphs in which edges are undirected they connect two vertices without point in either direction. A simple graph, g, consists of a nonempty set of vertices, v(g), and a set of edges, e(g) An undirected edge has two vertices u v called its endpoints. Two vertices in a simple graph are said to be adjacent iff they are the endpoints of the same edge. An edge is said to be incident to each of its endpoints. The number of edges incident to a vertex v is called the degree of the vertex and is denoted by deg(v) We get that the average degree of men = |f|/|m| average degree of women.