Question

Graph Theory assistance please!!

A connected graph G contains k blocks and l cut vertices. What is the relationship between k and l.

So I think it should be that k=l+1 But I am not sure if that is right or how to prove it.

Answer 1

it might be k=l+2

Answer 2

I don't really know what the words mean exactly, but if I have one loaf of bread, it has zero cuts and if I slice it in half I have two pieces and one cut. So pieces = cuts + 1 seems right to me based on this thinking haha.

Answer 3

it definitely is not k=l+1 I now ewalize

Answer 4

right thinking, but there are two ends to every piece of bread right?

Answer 5

I just found a theorem, and a counter example

Answer 6

that is the only reason I now know

Answer 7

I mean I am not entirely sure what we're talking about here, it's just my guess haha. I don't know what blocks or cut vertices are.

Answer 8

oh, yea, that makes things more difficult haha

Answer 9

so here listen to this "Every two distinct blocks of G have at most one vertex in common; and if they have a vertex in common, then this vertex is a cut-vertex of G"

Answer 10

What's a distinct block of G?

Answer 11

on a graph with 3 cut vertices, we had 5 blocks

Answer 12

a block is the biggest section you can cut off from a graph at the cut vertex

Answer 13

So basically that means that these are like the final strand left to separate the graph into two separate graphs then?

Answer 14

eg

Answer 15

so u,w and y are cut vertices

Answer 16

I think I see now.

Answer 17

So the number of edges at the cut vertices will be the number of graphs we get after we cut it there I think.

Answer 18

the blocks are