# 15-344/Classnotes for Tuesday September 15

We mostly went over Day One Handout today.

Dror's notes above / Students' notes below |

## Lecture Note for September 15

**DEFINITION 1** **Graph** A graph is a set (usually finite, "vertices")
along with a set ("edges") of unordered pairs of distinct elements of
.

**DEFINITION 2** **Incident** If an edge , we say that is incident to
*and* .

**DEFINITION 3** **N-valent** In a graph , a vertex is called
bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where .

**DEFINITION 4** **Edge Cover** An edge cover for graph is a subset such that every edge of incident to at least one vertex in .

**DEFINITION 5** **Independent** Let be a graph. A subset is called independent if whenever , then .

**THEOREM 1** Edge covers are complementary to independent sets. In other words, is an edge cover if and only if
the complementary subset is an independent set.

* Proof*
Assume is an edge cover. I assert that is independent.
Indeed, if , then since is an edge cover, either or
, which implies does not connect any two elements of .

Assume is independent. Pick any edge . As is independent, does not connect any two members of . Hence, either or , which implies is incident to an element of . QED

**DEFINITION 6** **Matching** is a subset of edges of a graph where no two edges share a common vertex. A matching is said to be perfect if
all edges in a graph are matched.

## Scanned Lecture Notes for September 15