Exercises
Multiple Choice
Articles
Open Problems
Login
12 items
Tagged:
connectivity
x
Start over
- to expand, or dig in by adding more tags and revising the query.
Sort By:
trending ▼
date
0
Undergraduate
By
Shiva Kintali
on July 30, 2012 | Updated Dec. 6, 2017
k-regular bipartite graphs are 2-connected
Prove that every connected \(k\)-regular bipartite graph on at least three vertices is 2-connected.
Mathematics
Graph Theory
bipartite graph
connectivity
0
Graduate
By
Shiva Kintali
on June 6, 2012 | Updated Dec. 6, 2017
Minimum Flip Connectivity Problem
Let \(G(V,E)\) be a directed graph such that if \(e=(u,v) \in E\) then \((v,u) \notin E\), i.e., \(G\) is an orientation of the underlying undirected graph. Consider the following operations : …
Computer Science
Mathematics
Algorithms
Graph Theory
connectivity
0
Undergraduate
By
Shiva Kintali
on June 5, 2012 | Updated Dec. 6, 2017
Properties of Petersen Graph
Petersen Graph is the graph shown below : Prove the following properties of the Petersen Graph : It is not planar. It is strongly-regular. It has a Hamiltonian path but no Hamiltonian Cycle. It i…
Mathematics
Graph Theory
connectivity
hamiltonian cycle
matching
petersen graph
0
Graduate
By
Shiva Kintali
on Dec. 3, 2012 | Updated Dec. 6, 2017
2-connectivity and bipartite minors
Prove that for every integer \(t\) there exists an integer \(n\) such that every 2-connected graph on at least \(n\) vertices has either a cycle of length at least \(t\) or a \(K_{2,t}\) minor.
Mathematics
Graph Theory
connectivity
graph minors
0
Undergraduate
By
Shiva Kintali
on Oct. 3, 2013 | Updated Jan. 4, 2018
Regular planar graphs
Prove or disprove : For each \(n\in \mathbb{N}\), there is a simple connected \(4\)-regular planar graph with more than \(n\) vertices. Prove that a planar, simple, connected, \(6\)-regular graph…
Mathematics
Graph Theory
connectivity
planar graphs
regular graphs
0
Graduate
By
Shiva Kintali
on July 28, 2012 | Updated Dec. 6, 2017
Petersen’s theorem
Prove that every 2-edge-connected 3-regular graph has a perfect matching
Mathematics
Graph Theory
connectivity
matching
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Dec. 6, 2017
Basics of Connectivity
Prove that a connected graph \(G\) with \(2k\) odd vertices (odd degree vertices) decomposes into \(k\) paths (not necessarily simple paths) if \(k > 0\). Does this remain true if \(G\) is not connec…
Mathematics
Graph Theory
basics
connectivity
0
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Dec. 6, 2017
Halin's theorem and Mader's theorem
Prove the following : Halin's Theorem : (Easy) There is a node of degree \(k\) in any edge-minimal \(k\)-vertex-connected graph. Mader's Theorem : (Hard) In any edge-minimal \(k\)-vertex-connected …
Mathematics
Graph Theory
connectivity
0
Undergraduate
By
Shiva Kintali
on June 17, 2012 | Updated Dec. 6, 2017
Edge connectivity vs Strong connectivity
A directed graph \(D\) is strongly connected if and only if \(\forall\) \(u,v\) there exists a directed path from \(u\) to \(v\). Prove that for an undirected graph \(G\) the following two are equival…
Mathematics
Graph Theory
connectivity
0
Undergraduate
By
Shiva Kintali
on June 14, 2012 | Updated Dec. 6, 2017
Connectivity of cubic graphs
Prove that if \(G\) is 3-regular graph, then its vertex-connectivity equals its edge-connectivity.
Mathematics
Graph Theory
connectivity
1
2
next page »
icon
Sign In or Sign Up
icon
Invite Friends
Post Something
x
Select What You'd Like To Post
POST AN ARTICLE
POST AN OPEN PROBLEM
POST AN EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Articles
Open Problems
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
bipartite graph
matching
graph labeling
dynamic programming
adjacency matrix
matrices
matrix multiplication
counting
extremal graph theory
interview question
Topics
Algebra
Algorithms
Approximation Algorithms
Calculus
Combinatorial Optimization
Combinatorics
Complexity Theory
Data Structures
Discrete Mathematics
Game Theory
Geometry
Graph Theory
Linear Algebra
Linear Programming
Logic
Mathematical Analysis
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×