Discrete Graphs

Graph

an ordered pair G=(V,E) where V is a nonempty finite set, and E is a set of two-element subsets of V.

Adjacent. Let G=(V,E) be a graph, and let u,v ∈ V

u is adjacent to v if {u,v} ∈ E.

Adjacent notation

{u,v} and u~v

Endpoints, {u,v} ∈ E.

u and v are endpoints of the edge

Edge of a graph

two-element subset of the vertex set

Incident (on or with) for {u,v} are an edge

u and v are incident with {u,v}

Thrm: If G=(V,E) is a graph, then ∑_v∈V d(v)=

2|E|

Correlary from ∑_v∈V d(v)=2|E|

The number of vertices of odd degree must be even

Degree. Let G=(V,E) be a graph, and let v ∈ V

d(v) is the number of edges with which v is incident

△(G)

max degree of a vertex in G

δ(G)

min degree of a vertex in G

Regular graphs

All vertices in G have the same degree

Order of G

the number of vertices in G, |V|

Size of G

the number of edges in G, |E|

Vertex set and edge sets of G

V(G) and E(G)

Complete graph

All pairs of distinct vertices are adjacent in G, denoted K_n

Type of graph: Path

a single open path of n vertices connected in a line

Type of graph: Cycles

C_n first and last vertices form an edge

Type of graph: Hypercube

dimensional cubes Q_n

Adjacency Matrix

V x V matrix, 1s denote a edge and 0 otherwise. Symmetric

~ relation name

is-adjacent-to relation defined on the vertex set of graphs

~ relation properties: reflexive? irreflexive?

no u~u false. generally no but vaculously true for edgless graph

~ relation properties: symmetric? antisymetric?

yes u~v => v~u works. generally no, but yes vaculously for edgless graph

~ relation properties: transitive?

generally no, but yes vaculously for edgless graph

vaculously

true because cant be proven false, the inital condition is false so we cant deny it

Subgraph ⊆

H is a subgraph of G if V(H) ⊆ V(G) and E(H) ⊆ E(G)

Induced Subgraph. Let G be a graph. ∈

Let A be a nonempty subset of V(G). The subgraph of G induced by A is the subgraph G[A], where V(G[A]) = A and E(G[A]) = {{x,y} ∈ E(G) : x,y ∈ A}

Clique and clique number. Let G be a graph. ⊆

A subset S⊆V(G) is a clique if G[S] is a complete graph. Clique number omega(G) is the largest cardinality of a clique in G.

Independent set and number. Let G be a graph. ⊆

A subset S⊆V(G) is an independent set if G[S] is a complete graph. The independent number alpha(G) is the largest cardinality of a clique in G.

Complement of graph G. ⊆ ≠

G-bar, where V(G-bar)=V(G) and E(G-bar)=E(G[A]) = {{x,y}: x,y ∈ V(G), x ≠ y, {x,y} not⊆ E(G)}

Prop a subset of V(G) is in a clique in G iff it is a _ in G-bar.

Independent set

alpha(G)=omega(_)

G-bar

Prop. If G is a graph with at least six vertices,

omega(G) >= 3 or omega(G-bar) >= 3