in Graph Theory
306 views
0 votes
0 votes
How many simple directed (unweighted) graphs on the set of vertices {v0,v1,…v5} are there that have at most one edge between any pair of vertices? (That is, for two vertices a, b, only at most one of the edges (a, b) and (b, a) is in the graph.)
in Graph Theory
306 views

1 Answer

1 vote
1 vote
Best answer

between any pair of vertices we can have atmost one edge that means we have 3 possibilities 

let verices pair is (u,v)

  1. No edge between u and v
  2. Edge from u to v
  3. Edge from v to u 

so no of pairs in 6 vertices graph = 6C2 

and each pair have 3 possibilities so no. of graphs possible = 3^(6C2)= 3^15

selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true