Graph Theory

Question 1

Total number of simple subgraphs possible from Kn(Complete Graph)

Answer 1

2^(C(n,2))

Question 2

Number of edges in Kn

Answer 2

C(n,2) = (n(n-1)/2)

Question 3

Cn is Bipartite if

Answer 3

n is Even
(In the Bipartite Graph, every cycle is an Even cycle)

Question 4

Max number of edges in Bipartite Graph

Answer 4

(n^2)/4 [for Complete Bipartite graph]

Question 5

Regular graph - every vertex same degree

Answer 5

Cn -> 2 regular

kn -> (n-1) regular

Nn -> 0 regular

Question 6

Isomorphic graphs - The same graphs drawn differently

Answer 6

same no. of : vertices, edges, degree sequence, cycle lengths

Adjacencies preserved

Question 7

Handshaking Lemma

Answer 7

Sum of degree(Vertices) = 2e

Question 8

Number of odd-degree vertices is

Answer 8

EVEN

Question 9

Can Kn be bipartite

Answer 9

Never

Question 10

number of vertices N-Cube graph

Answer 10

2^N

Question 11

degree of each vertex in the N-cube graph

Answer 11

N
(2 vertices are adjacent if they differ by 1 bit only)

Question 12

number of edges in the N-Cube graph

Answer 12

N * 2^(N-1)

Question 13

Trivial graph

Answer 13

1 vertex, no edge

Question 14

Complement of G(V,E)

Answer 14

G’(V,E’)

Question 15

Self Complementing graph

Answer 15

isomorphic to itself

Question 16

Edges in self-complementing graph

Answer 16

e = n(n-1)/4
i.e. (order%4==0) or {(order-1)%4==0}

Question 17

Walk

Answer 17

no edge repeat, a vertex may repeat

Question 18

Path

Answer 18

open walk, no vertex repeat

Question 19

Cycle

Answer 19

closed walk, no intermediate vertex repeats

Question 20

Component

Answer 20

maximal connected subgraph

Question 21

max no. of edges, n vertices, k components

Answer 21

(n-k)(n-k+1)/2

Question 22

Sufficient condition for connectedness

Answer 22

e > {(n-1)(n-2)}/2

Question 23

At least one of G or G’ is connected

Answer 23

True

Question 24

Every edge is a Cut-edge/ Bridge in

Answer 24

i) Tree
ii) Graph with no cycle

Question 25

Biconnected graphs

Answer 25

No cut-vertex/Articulation point
(all cycles are biconnected)

Question 26

Edge connectivity(λ)

Answer 26

Size of minimal cut set

(for cycle, λ>1)

Question 27

Vertex connectivity(Κ)

Answer 27

min no. of vertex removal disconnects the graph or leaves the trivial graph

Question 28

Κ <= λ <= δ <= 2e/v <= ∆

Answer 28

δ: min degree in the graph
∆ : max degree
e: the size of the graph
v: order of graph
Κ: vertex connectivity
λ: edge connectivity

Question 29

Whitney’s theorem

Answer 29

Κ <= λ <= δ