Toggle navigation
Mathematics
Vocabulary
Algorithms
trueshelf.org
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
0
High School
By
Shiva Kintali
on July 18, 2012 | Updated Jan. 16, 2017
Red Blue Hats
There are 10 people and 10 hats. Each person is assigned a random hat, colored either RED or BLUE, but the number of each colored hat is not known to them. They will be lined up such that each person …
Puzzles
Puzzles
logic puzzle
0
Undergraduate
By
diego
on June 8, 2012 | Updated Jan. 16, 2017
The cube of a connected graph is hamiltonian
Prove that the vertices of any connected graph \(G\) can be listed in a cyclic order so that the distance in \(G\) of every two consecutive vertices is at most \(3\). Moreover, show that this can be …
Computer Science
Mathematics
Algorithms
Graph Theory
hamiltonian cycle
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
Shiva Kintali
on June 6, 2012 | Updated Jan. 16, 2017
Algebraic dual of graphs
Let \(G\) be a connected graph. An algebraic dual of \(G\) is a graph \(G'\) such that \(G\) and \(G'\) have the same set of edges, any cycle of \(G\) is a cut of \(G'\), and any cut of \(G\) is a cyc…
Mathematics
Graph Theory
matroids
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
Basics of Hamiltonicity
Let \(G(V,E)\) be a simple graph with \(n\) vertices and minimum degree \(\delta\). Also, for every two vertices \(x, y \in V\), \(|N(x) \cup N(y)| + \delta \ge n + 10\). Prove that \(G\) has a Hami…
Mathematics
Graph Theory
basics
hamiltonian cycle
0
Undergraduate
By
Shiva Kintali
on May 31, 2013 | Updated Jan. 16, 2017
Characterizations of Eulerian graphs
It is well-known that a graph is Eulerian if and only if every vertex has even degree. Prove the following alternate characterization of Eulerian graphs Prove that if \(G\) is Eulerian and …
Mathematics
Graph Theory
eulerian graph
0
Undergraduate
By
aa1062
on July 22, 2012 | Updated Jan. 16, 2017
Prisoners finding numbers
A prison contains \(n\) prisoners, labeled \(1, 2, 3, \dots, n\). One day the warden announces that he is going to set up a room with \(n\) drawers in it, labeled \(1, 2, 3, \dots, n\). He will then …
Puzzles
Puzzles
strategy
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
Graduate
By
Shiva Kintali
on Aug. 8, 2012 | Updated Jan. 16, 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
« previous
1
2
3
...
23
24
25
26
next page »
icon
Sign In or Sign Up
icon
Invite Friends
×