Discrete Math

Front 1

Undirected graph

Back 1

An undirected graph G is a finite set of vertices V[G] and a finite set of edges E[G], along with a function i: E[G] --> V[G] x V[G]. For any edge e€E[G], if i(e) = (a,b), we say that vertices a and b are joined by edge e.

Front 2

Directed graph

Back 2

A directed graph G is a finite set of vertices V[G] and a finite set of edges E[G], along with a function i: E[G] --> V[G] x V[G]. For any edge e€E[G], if i(e) = (a, b), we say that edge e joins vertex a to vertex b.

Front 3

Isomorphic graphs

Back 3

Let G be a graph with vertex set V[G] and edge set E[G], and let H be a graph with vertex set V[H] and edge set E[H]. Then G is isomorphic to H if there are one-to-one correspondences (alpha): V[G] --> V[H] and (beta): E[G] --> E[H] such that, for any edge e€E[G], e joins vertex v to vertex w iff beta(e) joins vertex alpha(v) to vertex alpha(w).

Front 4

Path

Back 4

Let G be a graph. A path in G is a sequence v[0], e[1], v[1], e[2], v[2],..., v[n-1], e[n], v[n] of vertices v[i] and edges e[i] such that edge e[i] joins vertex v[i-1] to vertex v[i], where n>=1.

Front 5

Circuit

Back 5

A circuit is a path with v[0]=v[n]

Front 6

Simple

Back 6

A path or circuit is simple if the edges in the sequence are all distinct

Front 7

Connected

Back 7

A graph is connected is there is a path connecting any two pairs of vertices

Front 8

Tree

Back 8

A tree is a graph T with a specified vertex r, called the root, with the property that, for any vertex v in T where v!=r, there is a unique simple path from r to v.

Front 9

Degree

Back 9

Let G be an undirected graph, and let x€V[G] be a vertex. Let D[1] be the set of all edges e€E[G] such that such that i(e)=(x,b) for some b, and let D[2] be the set of all edges e€E[G] such that i(e)=(a,x) for some a. Then the degree of x is |D[1]| + |D[2]|.

Front 10

Outdegree

Back 10

Let G be a directed graph, and let x€V[G] be a vertex. Let D be the set of all edges e€E[G] such that i(e)=(x,b) for some b. Then the outdegree of x is |D|.

Front 11

Indegree

Back 11

Let G be a directed graph, and let x€V[G] be a vertex. Let D be the set of all edges e€E[G] such that i(e)=(a,x) for some a. Then the indegree of x is |D|.

Front 12

Euler path

Back 12

A simple path using all the edges of the graph.

Front 13

Euler circuit

Back 13

A simple circuit using all the edges of the graph