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
Connectivity of dual graph
Prove that if \(G\) is a simple 3-connected planar graph with at least 4 vertices, then the dual of \(G\) is also a simple 3-connected planar graph.
Mathematics
Graph Theory
planar graphs
0
Graduate
By
Shiva Kintali
on Feb. 20, 2013 | Updated Jan. 16, 2017
Treewidth and Cliques
A tree decomposition of a graph \(G(V, E)\) is a pair \(\mathcal{D} = ({X_i\ |\ i \in I}, T(I, F))\) where \({X_i\ |\ i \in I}\) is a collection of subsets of \(V\) (called bags) and \(T(I, F)\) is a …
Mathematics
Graph Theory
treewidth
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
Graduate
By
Shiva Kintali
on June 7, 2012 | Updated Jan. 16, 2017
Planar Graphs are Pfaffians
Let \(G(V,E)\) be an undirected graph. An orientation of \(G\) is Pfaffian if every even cycle \(C\) such that \(G \setminus V(C)\) has a perfect matching, has an odd number of edges directed in eithe…
Mathematics
Graph Theory
pfaffian
planar graphs
0
Undergraduate
By
rizwanhudda
on Aug. 24, 2012 | Updated Jan. 16, 2017
Second Minimum spanning tree
Given an weighted undirected graph \( G = (V, E)\), and \(w : E \mapsto R^+\). Let T be MST i,e minimum spanning tree of graph G. Second MST is a Tree T' different from T, and its weight is less t…
Computer Science
Mathematics
Algorithms
Graph Theory
trees
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
Chandra Chekuri
on July 29, 2012 | Updated Jan. 16, 2017
Diameter and low-degree vertex
Let \(G = (V,E)\) be an undirected connected graph. Suppose \(G\) has a pair of nodes \(s,t\) that are distance \(d\) apart. Show that there is a vertex \(v\in G\) such that the degree of \(v\) is at…
Computer Science
Mathematics
Algorithms
Graph Theory
counting
0
Undergraduate
By
Shiva Kintali
on June 29, 2012 | Updated Jan. 16, 2017
Coloring Planar Graphs
Prove that every planar graph has at least one vertex of degree at most five. Conclude that planar graphs are six-colorable. Prove that every triangle-free planar graph has at least one vertex of deg…
Mathematics
Graph Theory
eulers formula
planar graphs
0
Undergraduate
By
Shiva Kintali
on June 25, 2012 | Updated Jan. 16, 2017
Separator number of a tree
Let \(T(V,E)\) be a tree with \(|V| = n\) vertices. Let \(W\) be a subset of \(V\). Prove that there is a vertex \(v \in V\) such that every component of \(T - v\) contains at most …
Computer Science
Mathematics
Algorithms
Graph Theory
trees
0
Undergraduate
By
domotorp
on June 18, 2012 | Updated Jan. 16, 2017
Volley planning
Suppose there are n soldiers in a row who want to fire at the same time. Each of them has a constant memory and can only communicate with its neighbors, i.e. send message to left or right one and rece…
Puzzles
Puzzles
communication complexity
« 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
adjacency matrix
matrices
matrix multiplication
matching
sorting
math puzzle
imo
imo 2016
polynomials
basics
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
×