Combinatorics

Summary.

• graphs are defined by sets, not by diagrams

• deleting a vertex or edge

• how to use proofs by induction on graphs

• Euler's handshaking lemma

• graph invariants, distinguishing between graphs

• labeled and unlabeled graphs

• random graphs

• Important definitions:

  • graph, vertex, edge

  • loop, multiple edge, multigraph, simple graph

  • endvertex, incident, adjacent, neighbour

  • degree, valency, isolated vertex

  • subgraph, induced subgraph

  • complete graph, complement of a graph

  • isomorphic graphs, isomorphism between graphs

• Notation:

  • $\displaystyle u \sim v$

  • $\displaystyle uv$

  • val$(v)\text{,}$ deg$(v)\text{,}$ $d(v)\text{,}$ $d_G(v)$

  • $G\setminus\{v\}\text{,}$ $G\setminus\{e\}$

  • $\displaystyle K_n, G^c$

  • $\displaystyle G_1 \cong G_2$