combinatorics Flashcards
order of a graph
n, number of vertices
size of a graph
m, number of edges
trivial graph
order 1
empty graph
size 0
complete graph
every pair of vertices is connected
degree of a vertex
the number of vertices connected to vertex
delta G
max degree of G
S(G)
min degree of g
if G is a graph of size m, the sum of the degrees of v =
2m
any graph has a ___ number of vertices with odd degrees
even
isomorphic
if uv are adjacent in G, then they’re adjacent in H
bipartite graph
if vertices can be partitioned into two sets, and if uv is an edge, u and v are not in the same set
size of a bipartite graph of order n is
at most ceil(n/2)*floor(n/2)
the size of a bipartite graph is <=
ceil(n^2/4)
size of a bipartite graph =
ceil(n^2/4) iff n is even
No bipartite graph contains a
triangle
if size of a graph is > ceil(n^2/4)
G has c3 as a subgraph
a degree sequence is not a sequence of a graph when
sum of degrees is odd, or if one of the degrees is greater than the number of vertices of the graph
erdos gollci theorem
a degree sequence is graphical iff the sum is even and the sum from 1 to k [degrees] <= k(k+1) + sum k+1 to n [min(k, d)]
u-v walk
sequence of vertices beginning with u and ending with v
u-v trail
walk where no edge is traversed more than once
u-v path
walk where no vertex is visited more than once
circuit
closed trail of length 3 or more
adjacency matrix of a graph
nxn matrix where aij is 1 if vi,vj is an edge, 0 if not
incidence matrix of a graph
nxm matrix where bij is 1 if v incident to an edge, 0 otherwise
d(u,v)
min length of a u-v walk
eccentricity of a vertex e(u)
max distance u is from another vertex
diameter of graph
max eccentricity
radius of graph
min eccentricity
central vertex u
if eccentricity(u) = diameter(G)
center of G
subgraph created by all the central vertices
periphery of G
subgraph created by the not central vertices
rad G <= ? <= ?
diam(G), 2rad(G)
if T is a tree of order n, size m, then m =
n-1
a degree sequence of a tree if
sum of degrees = 2n-2
a set of vertices u in a graph is independent if
no edges between vertices of u
independence number of G
max number of vertices in an independent set
chromatic number X(G)
minimum amount of colors needed to give a proper coloring
clique number W(G)
order a largest complete subgraph
X(G) () W(G)
> =
Lames theorem
Iterations of Euclidean algorithm < lnb/lna + 1
