Graph Theory Notes

Jargons

  • Loop: An edge connecting a vertex to itself
  • Clique: A loop-free graph with every vertex connect to every other vertex
  • Vertices of attachment: For a subgraph H of a graph G, the v.o.a. are those vertices in H that have some incident edges in G not included in the subgraph H
  • Isthmus: An edge in a graph that has one of its ends of degree-1
  • Cutvertex: A vertex that its removal will make a connected graph/subgraph disconnected
  • Bridge: An edge that its removal will make a connected graph/subgraph disconnected
  • Cut: The set of edges that their removal will make a connected graph disconnected