- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

Let 'G' be a connected graph with 'n' vertices and 'm' edges. A spanning tree 'T' of G contains (n-1) edges.

Therefore, the number of edges you need to delete from 'G' in order to get a spanning tree = m-(n-1), which is called the circuit rank of G.

This formula is true, because in a spanning tree you need to have 'n-1' edges. Out of 'm' edges, you need to keep 'n–1' edges in the graph.

Hence, deleting 'n–1' edges from 'm' gives the edges to be removed from the graph in order to get a spanning tree, which should not form a cycle.

Take a look at the following graph −

For the graph given in the above example, you have m=7 edges and n=5 vertices.

Then the circuit rank is

G = m – (n – 1) = 7 – (5 – 1) = 3

Let 'G' be a connected graph with six vertices and the degree of each vertex is three. Find the circuit rank of 'G'.

By the sum of degree of vertices theorem,

n ∑ i=1 deg(V_{i}) = 2|E|

6 × 3 = 2|E|

|E| = 9

Circuit rank = |E| – (|V| – 1)

= 9 – (6 – 1) = 4

- Related Questions & Answers
- Circuit Switching
- Equivalent Circuit of an Induction Motor, Stator Circuit Model and Rotor Circuit Model
- Magnetic Circuit – Series and Parallel Magnetic Circuit
- Open Circuit and Short Circuit Test of Transformer
- Rank function in MySQL?
- Virtual - Circuit Network
- Electrical Circuit Devices
- Social Rank and its Usage
- Eulerian Path and Circuit
- What is Circuit Switching?
- What is the difference between a combinational circuit and a sequential Circuit?
- Short-Circuit Test and Open-Circuit Test on a Three-Winding Transformer
- History of the Integrated Circuit
- Short Circuit Assignment in JavaScript
- Short-circuit evaluation in JavaScript

Advertisements