Graph Theory

##### Distance Between Vertices and Connected Components of Graphs

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

Let

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

Disconnected

d_{G}(u,v) =∞ by convention ,when thereis no walk

**Note:** A graph G is connected if d_{G}(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.

##### 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(N_{n}) |
1 |

Cycle C_{n} |
2 if n is even 3 if n is odd |

Wheel W_{n} |
3 if n is even 4 if n is odd |

K_{n} |
n |

k_{m,n} |
2 |

**Properties:**

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

2. K_{n} 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.

##### 0Comment

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

##### 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

##### 0Comment

##### Perfect matching

Example:

find the no of perfect match in K_{6}

Sol:

n=3

=6!/2^{3}*3!

=6*5*4/8

=15