Toggle navigation
Mathematics
Sign In
Subscribe to the weekly news from TrueShelf
Subscribe
Sort By:
trending ▼
date
0
Undergraduate
By
rajeshchitnis
on Aug. 2, 2012 | Updated Jan. 16, 2017
Numbers divisible by sum of their digits
Show that there is an infinite sequence of natural numbers \({p_1,p_2,\ldots}\) such that for every \(i\in \mathbb{N}\) the number \(p_i\) does not have 0 as any of its digits but is divisible by the …
Mathematics
Puzzles
Number Theory
Puzzles
divisibility
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
TrueShelf Inc.
on Sept. 28, 2013 | Updated Jan. 16, 2017
Hamiltonicity of Line Graphs
Let \(G=(V,E)\) be a simple undirected graph. The line graph \(L(G)\) of \(G\) is defined as follows: Each vertex in \(L(G)\) corresponds to an edge in \(G\), and two vertices are connected by an edg…
Mathematics
Graph Theory
hamiltonian cycle
line graph
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
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
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
Undergraduate
By
JeffE
on June 6, 2012 | Updated Jan. 16, 2017
Longest increasing digital subsequence
Let \(S[1..n]\) be a sequence of integers between \(0\) and \(9\). A digital subsequence of \(S\) is a sequence \(D[1..k]\) of integers such that each integer \(D[i]\) is the numerical value of a sub…
Computer Science
Algorithms
dynamic programming
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
0
Undergraduate
By
TrueShelf Inc.
on Dec. 13, 2013 | Updated Jan. 16, 2017
Every edge in a triangle
For \(n \geq 3\), determine the minimum number of edges in a connected \(n\)-vertex graph in which every edge belongs to a triangle.
Mathematics
Graph Theory
triangles
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
« previous
1
2
3
...
23
24
25
26
next page »
icon
Sign In or Sign Up
icon
Invite Friends
×