Unit 4 - Graph Theory

In the incidence matrix of a graph, each row represents a:

• Vertex

• Edge

• Path

• Circuit

In the incidence matrix of a graph, each column represents a:

• Vertex

• Edge

• Loop

• Component

For a simple graph, the incidence matrix has entries of:

• 0 and 1 only

• 0, 1, and -1

• 1 and -1 only

• 0 only

If an edge connects vertex u and v, the incidence matrix has:

• 1 at row u and v

• 0 at row u

• 1 only at row u

• 2 at row u

What is the size of the incidence matrix for a graph with m edges and n vertices?

• n × m

• m × n

• n × n

• m × m

In an incidence matrix, a loop at a vertex contributes:

• 0

• 1

• 2

• -1

The sum of each column in the incidence matrix of an undirected graph is:

• 2

• 1

• 0

• Depends on the graph

A submatrix of A(G) helps identify:

• Circuits

• Paths

• Trees

• Subgraphs

Which of the following is NOT true about a submatrix of A(G)?

• It retains structure

• It can define induced subgraph

• It has same order as A(G)

• It is symmetric

Submatrix of adjacency matrix A(G) corresponds to:

• Induced subgraph

• Line graph

• Spanning tree

• Minimum cut