Graph Theory

Properties of degree(G)

1) The sum of all the vertex-degrees is twice the number of edges, an even number
   d(v1) + d(v2) ...+ d(vn) = 2(|E|) because every edge contributes two to the degree

2) The number of odd degree vertices in graph is always even, follows from 1)

3) The maximum degree in graph Δ(G) <= |V| - 1.

4) There are atleast two vertices of same degree in simple connected graph G(where V>=2)

Reason : If there are n vertices 1..n then possible degree are (0,1,...n-1) but since it is connected there can't be zero degree vertex so it is (1...n-1) but since there are n vertices and possible degrees only n-1 Hence at least two vertex need to have same degree

5) Degree sequence of graph is non increasing sequence of degree vertex
like it could be 3,3,2,2,1,1 but could not be 3,3,2,1 or 6,4,4,31 because in case of 3 3 2 1 we have odd number of odd degree vertices and in case of 6 4 4 3 1 the maximum degree(6) of graph is greater than |V| - 1

Properties for connectivity in graph

1) for G with n vertices n>=2 then G has atleast two non cut vertices
2) vertex connectivity or connectivity κ(G) size of minimum vertex cut or minimum number of vertices whose removal from G results in disconnected graph or a trivial graph

G is k-connected if its vertex connectivity k(G) >= k

means atleast k vertex need to be removed to make the graph disconnected

if G is k-connected then |V(G)| >= k + 1 m,n > 2 for complete graph k(Kn) = n-1
for cycle k(Cn) = 2 for peterson graphk(Pn) k(Pn) = 1 and k(Kmn) = min(n,m) complete graph on n vertices has edge connectivity of n-1
k(G) <= λ(G) < minimum degree(G) if there is always path between vertexes of odd degree

Matching M in Graph G is
set { } of pairwise {{a,b} {c,d}} non adjacent edges not sharing vertex

Counting Graphs
Number of graph with n vertices and e edges 
there are C(n,2) possible edges in connected graph on n vertices we have to select e of this edges this can be done in C(C(n,2),e) or we can choose from the basic definition like first edge can be selected from n vertices in C(n,2) ways second edge can be selected in C(n,2)-1 because we want simple graph without multiple edges so the first edge should not be selected again similarly

 C(n,2) * C(n,2)-1 * C(n,2)-2 * C(n,2)-3

and these edges can be selected in any order so we divide by 4!

Number of tress on n vertices
its the number of spanning trees or number of labeled trees which is n^n-2

Turan's Theorem 
Generalized statement
A n+1 vertex graph that does not contain any r+1 vertex clique or is Kr+1 free may be formed by partitioning the set of vertices into r parts of nearly equal size and connecting two vertices by an edge whenever they belong to different parts
maximum number of possible edges is T(n,r)=(r-1/r) (n^2)/2

Mantel Theorem
For case of r = 2 that is triangle free graph G, is special case covered by Mantel theorem
Maximum number of edges is n^2/4 n vetex triangle free graph with maximum number of edges e is almost complete bipartite graph
 example maximum number of edges in  triangle free graph G with 5 vertices has maximum 2*3 edges that is it is K(3,2) or n^/4 = 25/4=~6 edges
Corollary
any graph with more than n^2/4 edges has all cycle of length up to n that is 3 4 ...n length cycles.

Types of graph and their properties

n -cube  
each vertex has degree n and length of bitstring is n has 2^n vertices, assgined values of possible 2^n bitstring two vertices are adjacent if they differ in only one bit position sum of degree is n*2^n since each vertex has degree of n so number of edges would be (n/2)*2^n  = (2^n-1) *n

Complete graph Kn
complete graph on n vertices has Edges = n(n-1)/2 , since each vertex will be connected to remaining n-1 vertices maximally connected as we need to remove all n-1 vertices which disconnects the graph K1 to K4 are planar and every other complete graph is non planar

Cycle Cn for n>=3 cycle of n vertices vertices v1,v2,v3 .....vn are connected as {v1,v2},{v2,v3}... {vn,v1} every vertex of 2 degree |V| =|E|

Wheel Wn

Bipartite Graph
Simple graph G is bipartite if vertex set V can be divided in to two disjoint non empty set V1 and V2 and every  edge is between V1 and V2 only V1 and V2 are independent sets as no two vertices in V1 will be adjacent 2 colored graph

A graph with no odd cycle is bipartite as odd cycle would end connecting vertices in the same partitioned set so all tress are bipartite graph since there are no cycle or zero length cyles

Regular Graph
If every vertex of graph has same degree

Planar Graph
A finite graph is planar if and only if it does not contain a subgraph that is subdivison of K5 or K3,3 Planarity testing can be performed in O(n) time

Region is area bounded by subset of vertices, outside area of graph is also region therefore C3 has 2 regions and tree has 1 region.

For planar connected graph Euler theorem
v - e + r = 2

if we remove any edge from the cycle in graph we reduce the e and r by one but difference of e and r will always remain constant for planar graph


 For a connected planar simple graph following are the necessary but not sufficient condition This conditions we can derive from the Euler theorem

1)If v>=3 then e <=3v-6    // case when we have cycles of length 3 and greater
2)If v>3 and no cycles of length 3 then e <= 2v-4   //when we have cycle of length 4 and greater

For planar graphs this condition will hold but it might be the case that the inequality holds but graph is not planar, that is, non planar graphs can also satisfy the condition like K(3,3) satisfies the first inequality.



Problem Prove that if G is planar graph then it satisfies the condition e <= 3v-6
Solution

Let N be actual number of edges used to bound regions in graph G and r be actual number of regions in G then we have atleast 3 edge cycles, each region would be bounded by atleast 3 edge.

3r < = N

each edge is shared by two regions

N <= 2e ,

3r<=N <=2e

using r=e-v+2 we get

3(e-v+2) <=  2e

e <= 3v-6

Similary we can prove the second inequality also considering at least 4 length cycles
4r <= 2e
and r= e-v+2
reducing above equations we get e <= 2v-4


Relation between number of regions and edges 
Inequality holds for planar graph with at least C1 cycle length and e number of edges

C_l r  <= 2e

C_l least cycle in graph

e number of edges in graph

r number of regions in graph

Equality will hold only when either its on some 3 dimension like hexagons on football or when number of regions are infinite else it would be always less than 2e

Minimal Non Planar graphs
K5(with 5 vertices and 10 edges) and K(3.3) (6 vertices and 9 edges)

Maximal Planer
If by adding a single edge to planar graph it becomes non planer then we call it Maximal in triangular graph of n vertices we have 3v-6 edges and 2v-4 faces

Every non planar graph is supergraph of K5 or K(3,)

Problem Show that planar graph minimum degree of graph G is <= 5
Solution Assume it has minimum degree 6 then
then actual sum of degree >= 6n
2|e| >= 6n
|e| >= 3n
which contradicts planarity equation e<= 3n-6.

Problem If G is simple connected graph with |v| >= 11.Prove that G or its compliment G' must be non planar
Solution we prove it by contradiction Lets assume both G and G' are planar and x and y be number of edges in G and G' respectively
Since both are planar each should satisfy planar condition e<= 3v-6
G and G' has same number of vertices

x  <= 3n-6
y <= 3n-6

and also x+y  = n(n+1)/2
so n(n+1)/2 <= 6n -12
n<11 which is contradiction

Problem  G be simple connected planar graph with less than 12 vertices Prove that G has vertex of degree at most 4

Solution Assume G has vertex of degree greater than equal to 5 then
Sum of degree of vertices is = 2|e|
5n <= sum of degree of vertices = 2|e| <= 2(3n-6)
5n <= 6n-12
n >= 12

Problem Euler formula for planar graph with c components e edges v vertices r regions Connect the disconnected components of graph with single outer vertex from each component, the resulting graph is connected, number of regions r remains same, number of edges now are e+c-1
using Euler theorem now gives
v-(e+c-1)+r =2
v - e - c + r = 1


Problem Prove complete bipartite graph K(3,3) is not planar
Since K(3,3) doesnot have any odd length cycle and its complete that is each vertex in set is connected to all other vertex in other set
Assume K(3,3) be planar graph then from Euler theorem we get
e-v+2 = r
r= 9-6+2 = 5  ---------------(1

4r <= 2e     -------------------(2
4r because each region should be bounded by even length cycle of length > 4


reducing two equation gives
r<= 18/4 = 4.5
which leads to contradiction

Problem Prove that Petersen graph is not planar
Assume petersen graph is planar
Petersen graph has 5 length cycle so condition for region and edges now becomes
5r <=  2e
r <=  2/5 e
from Euler theorem we have e-v+2 = r
e-v+2 <= (2/5)e
Petersen graph has 10 vertices 15 edges which doesnot satisfy above condition Hence contradiction

Problem A soccer ball has pentagonal and hexagonal faces, and each vertex where these faces meet has degree exactly 3. Show that a typical soccer ball must have exactly 12 pentagonal faces.
Solution
This is the case when inequality  Cf <= 2e takes on equality condition.Because on spherical football there won't be any external boundary that we are undercounting
Consider x be number of hexagonal faces and y benumber of pentagonal faces
f = x+y i.e total number of face
each hexagon contributes 6 to the number of vertices and edges similarly pentagon contributes 5 to number of vertices and edges
we know that each vertex is  counted 3 times because they meet at 3 degree vertex
so  v = 5x+6y / 3  or 3v =5x+6y
Similarly for edges we know that
5x+6y = 2e
 we substitute all in Eulers equation f = e-v+2


www.math.ucdavis.edu/~momar/Assign4math145SolS10.pdf    //problem set


Connected Graph
A disconnected graph has atleast 2 components
At least one common node between two maximal path length because if there is no common node that would mean connecting two path would give new  maximal path which contradicts

Complement of disconnected graph
In complement of disconnected graph graph every vertex in component Ci is adjacent to every vertex in Cj.
Complement of disconnected graph will be always connected

Cut Set and Cut Vertices
Cut set is set of edges whose removal from G leaves G disconnected , its proper subset should not be cut set. Every cut set in a connected graph G must contain at least one branch of every spanning tree of G and so is the converse also true that is any minimal set of edges Q  containing one branch of every spanning tree than Q is cut set because removing Q from G would disconnect G and addition of any single edge would complete one spanning tree making it connected every circuit has even number of edges common with any cut set

Cut vertex is a vertex whose removal from G leaves G disconnected
A k vetex connected graph is graph in which at least k vertices need to be removed to make it disconnected
An isolated vertex is not cut vertex because it does not results in more connected components.
(Vertex) connectivity κ(G) of graph is minimum number of vertices whose removal from G makes it disconnected.

Connectivity of well known graphs
Kn donot have any cuts but by convention its connectivity is n-1
connectivity and edge connectivity of disconnected graph is 0
edge connectivity of kn = n-1 and also

Bounds on vertex and edge  connectivity
every graph has edge connectivity <=n-1
both edge connectivity and vertex connectivity  < = min(deg(G)) because deleting all the adjacent vertices of minimum degree vertex should disconnect it
κ(G) < λ(G) <= δ(G)

Problem Prove that κ(G) <= 2m/n where m is number of edges and n is number of vertices and n >=2
Solution Since κ(G)<=δ(G) also each vertex  has degree greater than or equal to δ(G) we can say that
n*δ(G) <= {sum over all vertices}deg(G) = 2|E|
n*δ(G) <= 2m
δ(G) <=2m/n

Problem Prove that in any graph G at least two vertices are not cut vertices
Solution  End points of the the maximal path in the graph will not be cut vertices
start with some vertex say u and take other vertex on end of maximal path from u. If we assume at most one vertex in a graph is not cut vertex, then one of the vertices u or v is cut vertex, which means removal of that vertex from graph leaves graph disconnected or in more connected components. Since each connected component will have atleast one vertex, say w,  that would mean w contains the maximal path uv which is contradiction

Problem If v is cut vertex of simple connected graph G Show that v is not cut vertex of its compliment G'
Solution
Since v is cut vertex it divides the graph in more than one connected component say Ci and Cj. In compliment of graph G every vertex in Ci will be connected to every other vertex in Cj. So v is not a cut vertex

Problem

Graph Coloring
vertex coloring is assigning colors to vertices in graph such that no two adjacent vertiex has same color
graphs are assumed to be loopless
A coloring using at most k colors is called k coloring
Chromatic number is smallest number of colors needed to color G
Subset of vertices assigned same color is called color class


Chromatic number for some well known graphs

• A graph of 1 vertex,that is, without edge has chromatic number of 1, minimum chromatic number

• A graph with one or more edge is at least 2 chromatic.

• Graph Kn is n-chromatic, any graph containing Kn will be at least n colorable

• Odd length cycle are 3-chromatic and even length cycle are 2-chromatic

• Every tree with two or more vertices is 2 chromatic

• 2 colorable graph are exactly bipartite graph trees and forests

• Every triangle free planar graph can be 3-colored

Limits on chromatic number

1<=x(G)<=n
For Planar graph (Four color Theorem)
Four color theorem states that every planar graph is 4 colorable
x(G) <= 4

Relation between degree of vertex and chromatic number
x(G)<= max-d(G) + 1

Relation between clique number ω(G) and chromatic number k(G)

k(G) >= ω(G) because vertices in clique form complete induced graph so each needs different color


Clique is set of vertices such that every two vertices in set are connected by an edge or we can say subgraph induced on this set of vertices is complete. like if we have vertices v1 v2 and v3 in clique then they form K3
clique number  ω(G) is number of vertices in maximum clique in G

No two vertices in independent set (Stable set) are adjacent  or each edge in graph has one endpoint in this set largest independent set is called independence number
Independence number denoted by beta(G) is number of vertices in largest independent set


Relation between independent set and color class
Each color class forms a independent set so
k coloring of graph = k partitions of independent set

Uniquely colorable graph
when only single partition of color classes possible

Vertex Cover

set of vertices such that all edges in graph are incident on atleast one of them or we can say that this set of vertices cover all the edges in the graph G.
vertex number is minimum number of vertex in vertex cover

finding minimum vertex cover is NP hard

Fig showing vertex cover of graph

In the figure above vertex set {7,6,4} is vertex cover because each of the edge has at least one endpoint in this set.while independent set states there should be at least one endpoint not in set S which is compliment of above set that is {1,2,3,5}

Vertex cover of some well known graphs
set of all vertices forms vertex cover that is they cover all the edges
end points of maximal matching forms vertex cover

Complete bipartite graph Kmn has minimum vertex cover of min{m,n}

Relation between Clique and independent set

Clique has edges between every pair of vertices in its set while independent set is just opposite with no vertices in the set should be connected
If we take complement of graph G whose clique set is S then in the complement of the graph this vertices will have no edges between them and so is independent set
Clique of graph G is independent set of G'

Relation between Independence number and chromatic number

Independence number denoted by beta is number of vertices in largest independent set
k-chromatic number graph forms k color classes so
maximum number of vertices in each color classs  <=  b(G)

 n/k <=b(G)

 Relation between vertex cover number and independence  number

A set of vertices is vertex cover if and only if its complement is an independent set, that is remaining set of vertices is independent set.
so total number of vertices in a graph(v) can be divided in to two partition sets of minimum vertex cover and maximum independent set

minimum vertex cover(G)  =  v - maximum independent set(G)
vertex cover number(G) = v - independence number(G)

Relation between chromatic number and minimum vertex cover
For planar graph: 
Let G be graph with n vertices
x(G) <=4  //follows from four color problem
independence number  I(G) >= n/4
n/4 <= n - (vertex cover number)  // relation between minimum vertex cover and independence number
minimum vertex cover <= 3n/4

Edge Cover
set of edges such that every edge of graph is incident to  at least one edge of set
complete bipartite graph Kmn has edge covering of max(m,n)
for a graph with isolated vertex there is no covering
covering for n vertex graph is >= ceil(n/2) edges
minimal covering of graph <= n-1 that is without cycles
minimal covering does not contains path of length greater than or equal to 3

Matching
set of edges no two sharing a common vertex
matching number ν(G) is size of maximum matching, that maximum number of such edges possible in graph G
perfect matching is matching in which matches all vertices of graph
perfect matching is maximum and maximal
In perfect matching edge cover number and matching number are both equal to |V|/2
If a graph has odd number of vertices no matching can touch them all because matching M always touches even number of vertices
If graph has odd number of vertices then we can form matching by selecting an edge and every alternate edge
every tree has at most one perfect matching
Qk has atleast 2^(2^k-2) perfect matchings

Perfect matching in Bipartite graph(Marriage Theorem)
Bipartite graph has complete matching if and only if |A|=|B| and for any subset of k nodes of A there are atleast k nodes of B that are connected to atleast one of them.
Implication : If every vertex in bipartite graph has same degree d than it has perfect matching and at least d distinct perfect matching.

Bipartite Graphs
Relation between maximum matching and minimum vertex cover
In bipartite graph number of edges in maximum matching equals number of vertices in minimum vertex cover


Petersen Graph
Graph with 10 vertices 15 edges 
Non planar, special case of non planar graphs that has both K(3,3) and K5 embeddings
Chromatic number of 3
Independence number 4
All vertices have degree 3
Contains 5-cycle which is not bipartite


Path and circuits
Hamilton Path  a path that visits each vertex exactly once
Determining whether path exist is NP complete problem
closure of graph is uniquely constructed from G by successively adding for all non adjavent

How many edges a graph should have to be hamiltonian  ?
A simple graph has hamilton path if each vertex has degree >= n/2
For all pair of non adjacent vertices u,v
d(v)+d(u) >= n

Euler Circuit and Path
Euler Circuit in graph G is simple circuit containing every edge of G
An Euler path in G is simple path  containing every edge of G

Necessary and sufficient condition for Euler path and Circuit
If all of the vertices of graph has even degree than it has Euler circuit
A connected multigraph has an Euler path but not Euler circuit if and only if it has exactly vertices of odd degree

References

Graph theory with application by Narsing Deo
Graph Theory in Discrete Mathematics by Rosen
www.geometer.org/mathcircles/graphprobs.pdf
http://www.mpi-inf.mpg.de/~pascal/graphtheory_exercises.html  --very good set of questions , with solutions
www.math.udel.edu/~lazebnik/papers/688hwsols.pdf    --graph theory and combinatorics part 1
http://www.math.udel.edu/~lazebnik/papers/689H1-4S.pdf  --graph theory and combinatorics part 2