29.2.4. Incidence Matrix

Try these first

1. 1.

   What is an incidence matrix?

   Hint

   Think about the structure that represents connections.

2. 2.

   Define a graph complement.

   Hint

   Invert the edges!

3. 3.

   What does an incidence matrix represent?

   • Edges only
   • Vertices only
   • Relationships between vertices and edges

   Hint

   Think of it as a bridge between vertices and edges.

4. 4.

   True or False: Every complete graph has an incidence matrix which is fully populated.

   • True
   • False

   Hint

   Consider how many vertices can connect.

5. 5.

   A complete bipartite graph K(3,3) has what kind of incidence matrix?

   Hint

   Sketch the bipartite graph first.

6. 6.

   Show that if G has 5 vertices and is connected, the graph’s complement G’ has how many edges?

   Hint

   Consider the total edges possible in a complete graph first.