virtualgate's picture

Graph Theory

Definition of a Graph
Content covered: 

Definition of a Graph

More Less
3Comments
Families of Graphs
Content covered: 

Families of Graphs

More Less
0Comment
Connected and Regular Graphs
Content covered: 

Connected and Regular Graphs

More Less
0Comment
Sum of Degrees is ALWAYS Twice the Number of Edges
Content covered: 

Sum of Degrees is ALWAYS Twice the Number of Edges

More Less
0Comment
Adjacency Matrix and Incidence Matrix
Content covered: 

Adjacency Matrix and Incidence Matrix

More Less
0Comment
Basic Problem Set
Content covered: 

Basic Problem Set 

More Less
0Comment
Basic Problem Set
Content covered: 

Basic Problem Set

More Less
0Comment
Spanning and Induced Subgraphs
Content covered: 

Spanning and Induced Subgraphs

More Less
0Comment
Degree at Least Two Means a Cycle Exists
Content covered: 

Degree at Least Two Means a Cycle Exists

More Less
0Comment
Basic Graph Theory Problem Set
Content covered: 

Basic Graph Theory Problem Set

More Less
0Comment
Distance Between Vertices and Connected Components of Graphs

 

If there is walk (and  hence a path from u to vin given graph G).

Let 

dG(u,v)= min { k  | u --- k-->v} be the distance between u and v.

 Disconnected

dG(u,v) =∞ by convention ,when thereis no walk

 

Note: A graph G is connected if dG(u,v) <∞ for all u,v∈G and disconnected otherwise.

The maximal connected sub graphs of G areits connected components

     c(G)=# of connected component of G

here c(G) is 2.

 

what maximality condition mean is ?

Maximality condition means that a sub graph H ⊆ G is a connected sub graph and for any w ∈ V(G) w ∉ H

then G[V(H) ∪{w}] is disconnected.

Contributor's Info

Created:
0Comment
Euler Trails and Euler Tours
Content covered: 

Euler Trails and Euler Tours

More Less
0Comment
Euler Trail iff 0 or 2 Vertices of Odd Degree
Content covered: 

Euler Trail iff 0 or 2 Vertices of Odd Degree

More Less
0Comment
Hamiltonian Graphs and Problem Set
Content covered: 

Hamiltonian Graphs and Problem Set

More Less
0Comment
Hamiltonian Graph Problems
Content covered: 

Hamiltonian Graph Problems

More Less
0Comment
Degree Sequences and Graphical Sequences
Content covered: 

Degree Sequences and Graphical Sequences

More Less
0Comment
Complement of a Graph
Content covered: 

Complement of a Graph

More Less
0Comment
Maximum vs Maximal
Content covered: 

Maximum vs Maximal

More Less
0Comment
Eccentricity, Radius & Diameter
Content covered: 

Eccentricity, Radius & Diameter

More Less
0Comment
Number of Cut-Vertices
Content covered: 

Number of Cut-Vertices

More Less
1Comment
Vertex Colouring
Content covered: 

Vertex Colouring

More Less
0Comment
Graph Coloring

Graph Colouring: Coloring the vertices of a graph such that no two adjacent vertices have the same colour.

 

Chromatic Number(X(G)): The Min no of colour required to colour thegiven graph G.

 

Graph(G) Chromatic Number X(G)
Null(Nn) 1
Cycle Cn

2     if n is even

3    if n is odd

Wheel Wn

3   if n is even

4   if n is odd

Kn n
km,n 2

 

Properties:

1. G is a graph with n vertices then X(G) <= n

2. Kn is a sub graph of Graph G X(G) >= n

3. X(G) <=1+Δ , where Δ is max degree in the graph.

4. X(G) >= |v|/|v|-δ , 

where δ is min degree in the graph.

 

The following statement are equivalent 

1) G is bipaptite 

2) G is 2-colourable

3) Every cycle in G is even cycle.

 

 

Example 1:

 what is its chromatic number?

 

Solution:

 

first arrange in decending order of degree V1 ,V6,V2,V3,V4,V5

we will assign color c1 to  V1 ,V6 now coming to V2 it should be diff from V1 and V6 so we gave c2 to V2 and V3 now same will be follow for V4 and V5 we gave it c3.

therefore we need 3 color.

Contributor's Info

Created:
0Comment
2-Chromatic Graphs
Content covered: 

2-Chromatic Graphs

More Less
0Comment
Basic Bound on the Chromatic Number
Content covered: 

Basic Bound on the Chromatic Number

More Less
0Comment
Matching
Content covered: 

Matching

More Less
0Comment

  • This quiz contains 5 questions on the topic Topic Name
  • Learn well before you attempt the quiz

Difficulty Level:  intermediate
Some Importent points of graphs

1) Every path is bipartite.

 

2) Let G be a bipartite graph with partile set X and Y then

v∈ X deg(V) = ∑v∈ Y deg(V)

 

3)Theorem1: Let G be a graph in which all vertices have degree at least 2 then G contain a cycle.

Theorem2: If G is hamiltonian graph then any  super graph G' G⊆ G' where G' is obtained by adding new edges between non adjacent vertices of G then G' is also hamiltonian graph

 

Contributor's Info

Created:
0Comment
Perfect matching

 

 

Example:

find the no of perfect match in K6

 

Sol:

n=3

=6!/23*3!

=6*5*4/8

=15

Contributor's Info

Created:
0Comment