- A
**graph**is a pair of sets \(V, E\),**vertices**and**edges**. In our book we specify that \(V\) is non-empty and \(E \subseteq V \times V\) does not allow elements (edges) of the type \((v,v)\) (loops). - An edge \(e = (u,v) \in E\) can be denoted \( e = uv\) while \(u\) and \(v\) are the
**ends**(or end vertices) of \(e\). It is said that \(e\)**joins**\(u\) and \(v\). - We say that \(u\) and \(v\) are
**incident**with edge \(uv\). - Two vertices are
**adjacent**if they are end vertices of the same edge (an edge joins them). - Two edges are
**adjacent**when they have a common vertex. - The number of edges incident with a vertex is the
**degree**of that vertex, denoted \(\deg{v}\). - A vertex of even (odd) degree is called an even (odd) vertex.
- A vertex of degree 0 is
**isolated** - A
**pseudograph**allows multiple edges and loops. - \(G_1(V_1, E_1)\) is a
**subgraph**of \(G(V,E)\) if and only if \(V_1 \subseteq V\) and \(E_1 \subseteq E\). - The
**complete graph**on \(n\) vertices is denoted \(K_n\) and has the property that every two vertices are adjacent. - A
**bipartite graph**is one where the vertices can be partitioned into two sets \(V_1\) and \(V_2\) in such a way that every edge joins a vertex in \(V_1\) to a vertex in \(V_2\). (Note that there are no edges within \(V_1\) or \(V_2\).) - A
**complete bipartite graph**is one in which every vertex in \(V_1\) is joined to every vertex in \(V_2\). This is denoted \(K_{n,m}\) when \(|V_1| = n\) and \(|V_2| = m\). - Let \(d_1, \ldots, d_n\) be the degree of the vertices of a graph \(G\) ordered so that \(d_1 \geq d_2 \geq \cdots \geq d_n\). This is called the
**degree sequence**of a \(G\). - The sum of the degrees of any graph (or pseudograph) is \(2 |E|\) (credited to Euler). This implies that the number of odd vertices is even.
- The notation \(G \setminus {e}\) or \(G \setminus {v}\) represent the subgraph of \(G\) formed by removing \(e\) or \(v\) (and all edges incident with \(v\)).

- Draw all possible graphs on three vertices. How many edges are there in each graph? What are the degree sequences? Can you do this on pseudographs?
- Draw \(K_7, K_{3,4}, K_{2,6}\).
- For each of these degree sequences either draw the graph or explain why no such graph exists:
- \(100, 99, 98, \ldots 3, 2, 2, 2\)
- \(1,1,1,1,1,1\)
- \(6,6,4,2,2,2,1,1\)
- \(5,4,3,2,1,1\)
- \(4,3,2,2,1\)

- How many complete bipartite graphs are there with \(n\) vertices?
- Does there exist a graph with five vertices, every vertex incident with at least one edge, but no two edges adjacent? Explain.
- Is this graph bipartite?

- How about this one?

- * (next DC) Can you come up with a general method for this?
- Let \(G_0\) be the graph from problem 6. Draw \(G_0 \setminus {f}\). Draw \(G_0 \setminus {ab}\).

Follow up to the derangement video. (Since today is so literal.)