# 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 ${\displaystyle G=(V,E)}$ is a set ${\displaystyle V=\{a,b,...\}}$ (usually finite, "vertices") along with a set ${\displaystyle E=\{(ab),(bc),(bd),...\}}$ ("edges") of unordered pairs of distinct elements of ${\displaystyle V}$.

DEFINITION 2 Incident If an edge ${\displaystyle e=(ab)\in {E}}$, we say that ${\displaystyle e}$ is incident to ${\displaystyle a}$ and ${\displaystyle b}$.

DEFINITION 3 N-valent In a graph ${\displaystyle G=(V,E)}$, a vertex ${\displaystyle u\in {V}}$ is called bivalent if it is incident to precisely two edges and n-valent if incident to precisely n edges, where ${\displaystyle n=0,1,2,..}$.

DEFINITION 4 Edge Cover An edge cover for graph ${\displaystyle G=(V,E)}$ is a subset ${\displaystyle C\subset {V}}$ such that every edge of ${\displaystyle G}$ incident to at least one vertex in ${\displaystyle C}$.

DEFINITION 5 Independent Let ${\displaystyle G=(V,E)}$ be a graph. A subset ${\displaystyle I\subset {V}}$ is called independent if whenever ${\displaystyle a,b\in {I}}$, then ${\displaystyle (ab)\notin {E}}$.

THEOREM 1 Edge covers are complementary to independent sets. In other words, ${\displaystyle C\subset {V}}$ is an edge cover if and only if the complementary subset ${\displaystyle V-C}$ is an independent set.

Proof ${\displaystyle (\rightarrow )}$ Assume ${\displaystyle C}$ is an edge cover. I assert that ${\displaystyle I=V-C}$ is independent. Indeed, if ${\displaystyle e=(ab)\in {E}}$, then since ${\displaystyle C}$ is an edge cover, either ${\displaystyle a\in {C}\implies a\notin {I}}$ or ${\displaystyle b\in {C}\implies b\notin {I}}$, which implies ${\displaystyle e}$ does not connect any two elements of ${\displaystyle I}$.

${\displaystyle (\leftarrow )}$ Assume ${\displaystyle I=V-C}$ is independent. Pick any edge ${\displaystyle e=(ab)\in {E}}$. As ${\displaystyle I}$ is independent, ${\displaystyle (ab)}$ does not connect any two members of ${\displaystyle I}$. Hence, either ${\displaystyle a\notin {I}\implies a\in {C}}$ or ${\displaystyle b\notin {I}\implies b\in {C}}$, which implies ${\displaystyle e}$ is incident to an element of ${\displaystyle C}$. 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.