Toggle navigation
Mathematics
SAT
JEE
IMO
Vocabulary
Algorithms
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Self-complementary graphs
Let \(G\) be a self-complementary graph (i.e., \(G\) is isomorphic to its complement) on \(n\) vertices. Prove that \(n \equiv 0\ (mod\ 4)\) or \(n \equiv -1\ (mod\ 4)\). Prove that \(G\) has a cut…
Mathematics
Graph Theory
graph complement
0
Undergraduate
By
Shiva Kintali
on Aug. 12, 2012 | Updated Jan. 16, 2017
Finding perfect matching in bipartite graphs
Let \(G = (A,B)\) be a bipartite graph. Hall's theorem implies that \(G\) has a perfect matching if and only if \(|A| = |B|\) and for each \(X \subseteq A\), \(|X| \leq |\Gamma(X)|\), where …
Computer Science
Algorithms
matching
0
Undergraduate
By
TrueShelf Inc.
on Sept. 28, 2013 | Updated Jan. 16, 2017
Task assignment using Hall's Theorem
You are given a collection of tasks each of which must be assigned a time slot in the range {\(1,\dots,n\)}. Each task \(j\) has an associated interval \(I_j = [s_j,t_j]\) and the time slot assigned t…
Mathematics
Graph Theory
assignment
halls theorem
0
Undergraduate
By
Shiva Kintali
on May 19, 2013 | Updated Jan. 16, 2017
Large min-degree implies perfect matching
Let \(G\) be a bipartite graph with partitions \(X\) and \(Y\) such that \(|X|=|Y|=n\). The degree of each vertex in \(G\) is at least \(n/2\). Prove that \(G\) has a perfect matching.
Mathematics
Graph Theory
matching
0
Undergraduate
By
Shiva Kintali
on June 17, 2012 | Updated Jan. 16, 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 May 9, 2012 | Updated Jan. 16, 2017
$K_4$ subdivision and 3-colorability
Prove that every graph with no subgraph isomorphic to a subdivision of \(K_4\) is 3-colorable.
Mathematics
Graph Theory
graph coloring
0
Undergraduate
By
Shiva Kintali
on May 22, 2013 | Updated Jan. 16, 2017
Basics of bipartite graphs
Prove the following properties of bipartite graphs : Prove that a graph \(G\) is bipartite if and only if every subgraph \(H\) of \(G\) has an independent set consisting of at least half of \(V(H)\)…
Mathematics
Graph Theory
basics
bipartite graph
0
Graduate
By
diego
on Aug. 13, 2012 | Updated Jan. 16, 2017
Treewidth, the natural way
Given a graph \(G\), we define \(\mathrm{la}(G)\) as the smallest \(r\) such that \(G\) is a minor of some \(T\times K_r\), where \(T\) is a tree (and \(\times\) in this context is the cartesian produ…
Mathematics
Graph Theory
treewidth
0
Undergraduate
By
Jagadish
on Nov. 3, 2012 | Updated Jan. 16, 2017
Array to Histogram
Given an array A[1..n] containing integers between 1 to n, transform the array to contain counts of each number in their respective positions. Your algorithm should run in linear time and constant ext…
Computer Science
Algorithms
linear time algorithms
0
Undergraduate
By
aa1062
on July 22, 2012 | Updated Jan. 16, 2017
Pecking order
A researcher is studying the social dynamics of chicken coops. In each coop, for each pair of chickens \(A\) and \(B\), there is a pecking relationship: either \(A\) pecks \(B\) or \(B\) pecks \(A\) (…
Mathematics
Graph Theory
tournament
« previous
1
2
3
...
22
23
24
25
26
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 EXERCISE
POST A MULTIPLE-CHOICE QUESTION
Content Types
Exercises
Multiple-Choice Questions
Levels
High school
Undergraduate
Graduate
Subjects
Mathematics
Computer Science
Puzzles
Optimization
Trending tags
geometry puzzle
connectivity
planar graphs
regular graphs
counter example
hamiltonian path
path
digraphs
fermats little theorem
jee
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
Mathematics
Matrix Theory
Number Theory
Optimization
Probability
Programming
Puzzles
Randomized Algorithms
Real Analysis
Trigonometry
×