A graph is a pair G = (V, E) where V is a finite set called the set of vertices and E \subseteq p_2(V), E is called the set of edges of G.
only one vertex |V| = 1, E = \emptyset
all vertices are connected with each other K_n = (\{v_1, \cdots, v_n\}, p_2(\{v_1, \cdots, v_n\})). K_1 is therefore a trivial graph.
|p_2(\{v_1, \cdots, v_n\})| = \binom{n}{2} = \frac{n(n-1)}{2}
The degree of a vertex v in G is the number of edges containing v. \deg_G(v) = |\{e \in E(a): v \in e\}|
|E| = \frac{1}{2} \sum_{v \in V} \deg_G(v)
A path in a graph is a sequence of vertices (v_0, v_1, \cdots, v_k) such that:
A cycle in G is a path (v_0, \cdots, v_k, v_0) such that
A graph is said to be connected iff for every x, y \in V there is a x-y path in G, i.e. a path (v_0, \cdots v_k) such that v_0 = x, v_k = y. Otherwise it is called disconnected.
Graph is connected iff for every partition \{V_1, V_2\} of V such that V_1 \ne \emptyset and V_2 \ne \emptyset there exists v_1 \in V_1 and v_2 \in V_2 such that there is a v_1 - v_2 path in G
G is called Eulerian iff:
G = (V, E), H = (W, F) is called a subgraph of G if W \subseteq V and F \subseteq E. Denoted as H \preccurlyeq G, it is a poset.
If W = V then H is called a spanning subgraph of G.
If F = E \cap p_2(W) then H is called an induced subgraph of G.
A component of G is any maximal connected subgraph of G.
If G is a disconnected graph, \bar{G} is connected.
A complement of G = (V, E) (denoted by \bar{G}) is (V, \{u, v \in V : uv \notin E\}). In other words the edges are flipped: If 2 vertices were adjacent in G, they are not adjacent in \bar{G} and the other way around.
graphs that have the same structure. Hard to example mathematically. Please refer to wikipedia.
If \bar{G} is isomorphic to G then the graph is self-complementary
A graph G is called bipartite if the vertices can be divided into 2 disjoint and independent sets.
\delta(G) = \min(\{\deg(v) : v \in V\})
\Delta(G) = \max(\{\deg(v) : v \in V\})
If \delta(G) \ge 2 then G has a cycle
G is k-regular iff (\forall v \in V)(\deg(v) = k)
G is called a tree iff:
Every connected graph has a spanning tree
The following conditions are equivalent:
For a connected graph G = (V, E)
N = ((V, E), w) w: E \to \mathbf{R}^+
Find the cheapest spanning tree in N. A greedy naive way:
\kappa(G) = min\{k : there exists a k-element set S \subseteq V such that G - S is disconnected or trivial \}
For example: A tree has connectivity of 1, a complete graph K_n has connectivity of n-1
We call a graph a k-connected one when \kappa(G) \ge k
G is 2-connected iff for every x, y \in V(G) there exists a simple cycle C in G such that x, y \in V(C)
A Hamiltonian cycle in G is a spanning, simple cycle in G
G is a Hamiltonian graph iff G has a Hamiltonian cycle.
If G is Hamiltonian then:
If G has p vertices, p \ge 3, and (\forall v \in V)(\deg(v) \ge \frac{p}{2}) then G is Hamiltonian
(\forall \{x, y\} \notin E \implies \deg(x) + \deg(y) \ge p) \implies G is Hamiltonian
G is said to be planar iff G can be represented by a drawing in which no two edges intersect.
“parts” of a planar graph (K_4 has 4 facets)
Let G be a connected planar graph with with n vertices and k edges. Then, in every planar representation of G the number of facets, f satisfies the formula f = k - n + 2
For every planar graph G with k edges, n vertices, and f facets we have:
!\exists: there exists exactly one↩︎