Log In

Information Collected from multiple sources(primarily from Wikipedia, Wolfram Alpha and Narsingh Deo Textbook)









Matching, covering and Independent Set





If there is exactly 2 vertices of odd deg then there is a path joins these 2 vertices

Every cut set of a connected graph G includes at least one branch from every spanning tree of G.

no of vertices of odd degree is always even

Every circuit has an even number of edges in common with any cut set

If K components, then at most

(V-K)(V-K+1)/2 edges

A graph with one or more vertices is at least 2-chromatic.


 A graph consisting of simply one circuit with |V|>=3 is 2-chromatic if n is even and 3-chromatic if n is odd.

Independence Number+Vertex Covering Number = |V|


If no isolated vertices there, then

Matching Number+Edge Covering Number = |V|


Matching No<=Vertex Cover No<=2*Matching No

Cycle graphs with an even number of vertices are bipartite




In a connected graph G with exactly 2k odd vertices, there exist k edge-disjoint subgraphs such that they together contain all edges of G and that each is a unicursal graph






An open walk that includes (or traces) all edges of a graph without retracing any edge is called a unicursal line or open Euler line. A connected graph that has a unicursal line is called a unicursal graph


There is one and only one path between every pair of vertices in a tree T

No of edges = |V| - 1

Every edge of a tree is a cut set






Every tree is bipartite



All vertices are even degree



Eulerian trail if and only if exactly zero or two vertices have odd degree

  Eulerian cycle if and only if decomposed into edge-disjoint cycles



All vertices with nonzero degree belong to a single connected component






A planar bipartite graph is dual to a planar Eulerian graph and vice versa


If |V|%2==1 and |V| >=3


No of edge disjoint Hamiltonian circuits =



The number of different Hamiltonian cycles in a complete undirected graph on V vertices is (V − 1)! / 2 and in a complete directed graph on n vertices is (V − 1)!. These counts assume that cycles that are the same apart from their starting point are not counted separately.

A Hamiltonian graph on V nodes has graph circumference V.

a complete graph with more than two vertices is Hamiltonian

every cycle graph is Hamiltonian

every tournament has an odd number of Hamiltonian paths

every platonic solid, considered as a graph, is Hamiltonian

the Cayley graph of a finite Coxeter group is Hamiltonian

An Eulerian graph G (a connected graph in which every vertex has even degree) necessarily has an Euler tour, a closed walk passing through each edge of G exactly once. This tour corresponds to a Hamiltonian cycle in the line graph L(G), so the line graph of every Eulerian graph is Hamiltonian. Line graphs may have other Hamiltonian cycles that do not correspond to Euler tours, and in particular the line graph L(G) of every Hamiltonian graph G is itself Hamiltonian, regardless of whether the graph G is Eulerian.


A strongly connected simple directed graph with n vertices is Hamiltonian if the sum of full degrees of every pair of distinct non-adjacent vertices is greater than or equal to 2n − 1.


A simple graph with n vertices has a Hamiltonian path if, for every non-adjacent vertex pairs the sum of their degrees and their shortest path length is greater than n.

All Hamiltonian graphs are biconnected, but a biconnected graph need not be Hamiltonian (see, for example, the Petersen graph)

tournament (with more than two vertices) is Hamiltonian if and only if it is strongly connected


Bondy–Chvátal theorem

A graph is Hamiltonian if and only if its closure is Hamiltonian.



All planar 4-connected graphs have Hamiltonian cycles, but not all polyhedral graphs do

If the sums of the degrees of nonadjacent vertices in a graph G is greater than the number of nodes N for all subsets of nonadjacent vertices, then G is Hamiltonian


A simple graph with n vertices (n ≥ 3) is Hamiltonian if every vertex has degree n / 2 or greater


A graph with n vertices (n ≥ 3) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n or greater 


A strongly connected simple directed graph with n vertices is Hamiltonian if every vertex has a full degree greater than or equal to n.

Spanning Tree

Adding just one edge to a spanning tree will create a cycle; such a cycle is called a fundamental cycle (Fundamental circuits). There is a distinct fundamental cycle for each edge; thus, there is a one-to-one correspondence between fundamental cycles and edges not in the spanning tree. For a connected graph with V vertices, any spanning tree will have V − 1 edges, and thus, a graph of E edges and one of its spanning trees will have E V + 1 fundamental cycles.

A shortest spanning tree T for a weighted connected graph G with a constraint

Deg(Vi) for all vertices in T. for k=2, the tree will be Hamiltonian path

Every circuit of a connected graph G includes at least one link from every co spanning tree of G.







If the branches of the spanning tree T of a connected graph G are b1, . . . , bn−1 and the corresponding links of the co spanning tree T ∗ are c1, . . . , cm−n+1, then there exists one and only one circuit Ci in T + ci (which is the subgraph of G induced by the branches of T and ci)






Dual to the notion of a fundamental cycle is the notion of a fundamental cutset. By deleting just one edge of the spanning tree, the vertices are partitioned into two disjoint sets. The fundamental cutset is defined as the set of edges that must be removed from the graph G to accomplish the same partition. Thus, each spanning tree defines a set of       V – 1 fundamental cutsets, one for each edge of the spanning tree.



Emax =

|V| / 2


Only even length cycles


No of Perfect Matching in Kn,n = n!

Matching No = Vertex Cover No

If no isolated vertices there, then independence no = edge cover no

Min Vertex cover of Km,n = min(m,n)




E = |V|*





Number of Perfect Matching in K2n =

(2n)! / [2^n * n!]

And for

Kn = (2m-1)*(2m-3)*…*5*3*1

Where n=2m

Number of Perfect Matchings =

(|V| - 1) !



A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree


A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree

In a connected  isograph D of n vertices and m arcs, let W = (a1, a2,..., am) be an Euler line, which starts and ends at a vertex v (that is, v is the initial vertex of a1 and the terminal vertex of am). Among the m arcs in W there are n − 1 arcs that enter each of  n−1 vertices, other than v, for the first time. The sub digraph D1 of these n−1 arcs together with the n vertices is a spanning arborescence of D, rooted at vertex v.


Length of Directed Path =

Chromatic Number - 1


A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree

A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree,

A digraph is said to be disconnected if it is not even weak. A digraph is said to be strictly

weak if it is weak, but not unilateral.

It is strictly unilateral, if it is unilateral but not strong. Two vertices of a digraph D are said

to be

i. 0-connected if there is no semi path joining them,

ii. 1-connected if there is a semi path joining them, but there is no u−v path or v−u path,

iii. 2-connected if there is a u−v or a v−u path, but not both,

iv. 3-connected if there is u−v path and a v−u path.


Every planar graph with |V| has a nonplanar complement 


If both graph G and its graph complement G’ are planar, then G has eight or fewer vertices.

For a simple, connected, planar graph with V vertices and E edges and F faces, the following simple conditions hold for V ≥ 3:

  • E ≤ 3V − 6
  • If there are no cycles of length 3,  then E ≤ 2V − 4.
  • F ≤ 2V − 4.


Euler's formula

V − E + F = 2


Planar graph density

D = (E-V+1)/(2V-5)

D=0 → Completely Sparse graph

D=1 → Completely Dense graph




Kuratowski's theorem

a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 (the complete graphon five vertices) or of K3,3


Wagner's theorem

a finite graph is planar if and only if its minors include neither K5 (the complete graph on five vertices) nor K3,3 


A graph is planar if it has a combinatorial dual graph.

Only planar graphs have duals. 



posted Oct 24, 2018 in Discrete Mathematics
edited Sep 4, 2020 by


do we really need to learn so many things? Such stuffs are not even taught in IITs


Did you read the birthday attack question from GATE 2017 Paper?

That i found under the cryptography - in tanenbaum book
Did they teach Birthday Attack in any NPTEL video?
not sure about it. Haven't watched nptel videos? I went thru standard books.
is pdf of this is available to any one??

Srestha Sharma

Yes pdf is available

please kindly  forward it to [email protected] and [email protected] ,

Can you please forward link to download this chart


can you plz forward the pdf link of this chart on [email protected]
I typed this in MS Word.

@nephron plz share pdf here

plz someone mail me at [email protected]
if someone have pdf then upload it on drive and share link here
please someone mail me at [email protected]
can any one  please send this to  [email protected]
thanks in advance


Please share the link of the PDF of the above table here so that everyone can use it.