Here is a partial list of topics which will be on the midterm. Back to the class page. Extra points for finding misprints here!
Cliques and clique-numbers of graphs
H is a subgraph of G if VH is contained in VG
and EH is contained in EG. A subgraph H of G
is called a clique if it is a complete
subgraph which is not contained in any larger
complete subgraph (i.e., a maximal complete
subgraph). The largest number of vertices in
any clique of G is called the clique number
of G and denoted omega(G). Equivalently, it
is the largest number of elements in any set
of vertices which are pairwise adjacent in G.
The clique number of a bipartite graph is
either 1 or 2. Why? If G has n vertices,
what does it mean to say that omega(G) = n?
Matchings and bipartite graphs
Definition of bipartite graph: G is bipartite
if and only if its vertices can be divided into
two disjoint non-empty subsets V_1, V_2 so that
edges never join vertices from the same subset.
The pair V_1, V_2 is a bipartition of G.
A vertex v of G is said to be covered by M if
v is incident to some edge in M.
Note that G is bipartite if and only if it
contains no odd-length cycle.
A matching in G is a subset M of EG
such that no vertex in G is incident with more
than one edge from M. A matching M is called
perfect if every vertex is incident with
one (and only one) edge from M. If G is
bipartite, a matching M of G is called
full if there is some bipartition of G
such that every vertex in one of the two sets
V_1, V_2 is covered.
Thm.9.2.5
If G is bipartite and k-regular (k>0),
then G has a perfect matching.
If G is any graph which is bipartite and
k-regular (k>0) and if V_1, V_2 is any
bipartition of G, why must V_1 and V_2 have
the same cardinality?
Cor. (problem 8, p.358)
If G is bipartite and k-regular,
then G has k disjoint perfect matchings.
The following "match-making condition" (MMC)
was originally due to Konig and Hall and it
is clearly a necessary condition for a full
matching of some bipartite graph:
MMC If G is bipartite with bipartition
V_1, V_2 and if W is a subset of V_1, then
|Nbr_G(W)| \geq |W|,
where Nbr_G(W) is the set of all vertices in
G which are adjacent to one or more vertices
in W and "\geq" means "greater than or equal".
As usual |S| is just cardinality of S.
Thm. If G is bipartite and satisfies the MMC,
then G has a full matching.
(cf. pp. 347--349 in the text).
Thm. (Konig-Hall)
If G is bipartite and satisfies MMC,
then G has a full matching.
Can you show that the Konig-Hall Theorem implies
Thm. 9.2.5?
Two typical examples of bipartite graphs are
boys and girls (where edges mean marriage) and
people and machines (where edges mean the person
can operate the machine).
Every graph G can be made into a bipartite graph B
as follows: Let V(B) = VG U EG and let E(B) be the
set of all unordered pairs [v,e], where v is in VG,
e is in EG, and v is an endpoint of e. What are
the vertex degrees in B?
Extremal graph theory
Prop. If G has n-vertices, then |EG| \leq C(n,2),
where C(n,2) = n(n-1)/2 is n-choose-2.
Pf. Trivial (right?).
Thm. If G has n vertices and G is bipartite, then
|EG| \leq [n/2]{n/2},
where [n/2] is the floor-function of n/2,
and {n/2} is the ceiling-function of n/2.
This follows immediately from the following lemma:
Max{pq: p+q=n, p,q positive integers} = [n/2]{n/2}.
Pf of lemma: Let a = p - (n/2), so p = (n/2) + a.
Then q = n-p = (n/2) - a, so pq = (n/2)^2 - a^2.
This is as large as possible when a is as small as
possible. So for p = [n/2] or p = {n/2}, a = 0
or 1/2 depending on whether n is even or odd, and
this is the least possible value for a.
Cor. to the Thm.: If G is a graph and |EG| > n^2/4,
then G is not bipartite.
Interesting fact: If |EG| > n^2/4, then in fact G
must actually contain a triangle (not just an odd
cycle). So the largest possible number of edges
in any triangle-free graph is n^2/4.
Line graphs
If G is a graph with at least one edge, we define
LG by V(LG) = EG, with [e,f] in E(LG) if and only
if e,f are distinct edges in G which share a single
endpoint. That is, the vertices of the line graph
LG are the edges of the original graph G and edges
of G are adjacent as vertices of LG when they are
adjacent as edges in G.
For C_n, LC_n = C_n (for n at least 3). Also,
L(K_1,q) = K_q, where K_1,q is the star-graph with
one central vertex and q edges. What is LP_n?
Can any graph which is _not_ a cycle be isomorphic
to its line graph?
Can you find two non-isomorphic graphs with the
same line graph?
Forbidden subgraphs and planarity
G is bipartite iff G contains no odd cycle.
G is a forest iff G contains no cycle.
G is planar if it can be drawn without crossings
in the plane. K_4 is planar but K_5 is not. Also,
the 3-houses, 3-utilities graph K_3,3 is not planar.
(Just try to draw K_5 and K_3,3 and you'll see why.)
An elementary subdivision of a graph G is the graph
obtained from G by replacing some edge e=[v,w] by
two edges [v,*_e], [*_e,w] and adding one new vertex
*_e. Everything else stays the same. Call G and H
homeomorphic provided there exists a sequence
of graphs G_1, G_2, ... ,G_m such that G=G_1, H=G_m,
and for each successive pair G_i, G_(i+1) one is a
subdivision of the other. (That is, homeomorphism
is the smallest transitive relation which relates an
elementary subdivision to the original graph.)
Kuratowski gave the following characterization:
G is planar iff G contains no subgraph homeomorphic
to K_5 or K_3,3,
A graph is outerplanar if it can be drawn in the
plane without crossings and with every vertex on the
boundary of a single region.
G is outerplanar iff G contains no subgraph homeomorphic
to K_4 or K_2,3
Steiner triple systems
Definition - could you state it? Can you give an
example of 7 triples from a set with 7 elements?
What are the two algebraic constraints? WHat about
if you replace triples by quadruples?
Pigeon-hole Principle (PHP)
Simple examples and consequences - e.g., in any graph,
at least two vertices must have the same degree.
Principle of Inclusion/Exclusion PI/E
Simple examples ...
Back to the class page .