Graph Theory Notes

Jennifer

Sep 28, 2017

Concepts

Basics

• Graph: Nodes (vertices) and edges.
• Isolated: a node without an incident edge.

Type of Graphs

• Empty graph: no vertex.
• Multi-graph: 2 or more edges on the same pair of vertices.
• Simple graph: no loop, no parallel edges.
• Directed graph (digraph): each edge is represented by an ordered pair (directions of edges matter).
• Complete graph: simple; every vertex connected to every other distinct vertex.
• Bipartite graph: vertices can be partitioned into 2 disjoint subsets.
• Complete Bipartite graph: each node has an edge to every node in the other subset.
• Sub-graph: node and edge sets are subsets of a graph.

Degree

• Degree of a vertex: number of edges incident on this vertex; loops are counted twice.
• Total Degree of a graph:

Walk

(fromto)

• Walk: a finite alternating sequence of adjacent vertices and edges.
• Path: a walk with no repeated edge.
• Simple: a path with no repeated vertex other than the possibility that.
• Closed: a walk that starts and ends at the same vertex.
• Circuit: a closed path.
• Cycle: a simple circuit.
• Trivial Circuit: only one vertex, no edge.

Connectivity

• Connected (for two vertices): there exists some walk in between.
• Connected (for a graph): every two vertices are connected.
• Ifis a Connected Component of:
  • is a sub-graph of.
  • is connected.
  • is not a proper sub-graph of any connected sub-graph of.

Adjancency Matrix

• Out-degree

• In-degree

Path & Circuit

Hamiltonian Circuit

A closed walk of a graphthat contains:

• Non-repeated edges forming a subset of.
• Non-repeated vertices, except the same start/end vertex, forming the full set of.

Euler Path

Fromto;:

A path that starts atand ends at, passes every vertex, and traverse every edge ofexactly once.

Euler Circuit

A closed walk of a graphcontaining:

• Non-repeated edges forming the full set
• Possibly repeated vertices forming the full set

Tree

• Tree: a connected graph only containing trivial circuits.
• Acyclic Direct Graph: a directed graph without a non-trivial directed cycle.
• Leaf (Terminal Vertex) of a tree with 2 or more vertices: a vertex of degree 1.

Graph Isomorphism

A graphis isomorphic to another graphif and only if there exists two bijections mapping the vertex sets and edges sets respectively:

Theorems

1. The total degree of a graph equals twice the number of edges.
2. In any graph, the number of vertices of odd degree is even.
3. If,are vertices on a circuit in, then if one edge is removed from this circuit, there still exists a path in between.
4. Ifis connected and contains a circuit, then an edge of the circuit can be removed without disconnecting.
5. An Euler path fromtoexists ⇔is connected,andhave odd degree, and all other vertices ofhave even degree.
6. A graphcontains an Euler circuit ⇔is connected, and every vertex ofhas even degree.
7. Ifis a connected graph withvertices,, such thatfor any pair of nonadjacent verticesandin, thenhas a Hamilton circuit.
8. Any tree that hasvertex has at least one vertex of degree.
9. Any tree ofvertices hasedges.
10. If a connected graph hasvertices andedges, it is a tree.
11. If a graphcontains a Hamiltonian circuit, thenmust contain a sub-graphthat:
    • Is connected.