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\)