Graph theory discrete maths


#1

The number of distinct simple graphs with up to three nodes is
A. 15
B. 10
C. 7
D. 9


#2

The number of max edges a simple graph can have is n×(n−1)2n×(n−1)2.

So, for a graph with 3 nodes the max number of edges is 3.
Now there can be 0 edges, 1 edge, 2 edges or 3 edges in a 3 node simple graph.
So the total number of unlabled simple graphs on 3 nodes will be 4.
Similarly for two node graph we have option of 0 or 1 edge and for one node graph we have option of 0 edge.
So the total number of simple graphs upto three nodes are: 4+2+1=7.


#3

The number of max edges a simple graph can have is n×(n−1)/2

So, for a graph with 3 nodes the max number of edges is 3

Now there can be 0 edges, 1 edge, 2 edges or 3 edges in a 3 node simple graph.

So the total number of unlabled simple graphs on 3 nodes will be 4.

Similarly for two node graph we have option of 0 or 1edge.

So the total number of simple graphs upto three nodes are:

4+2+1=7


#4

Assume that the vertices are unlabelled. Number of distinct simple graphs with 1 node = 1
Number of distinct simple graphs with 2 nodes = 2
Number of distinct simple graphs with 3 nodes = 4
Therefore, total number of distinct simple graphs upto three nodes = 1+2+4=7.