Let G be a connected regular graph with n edges. How many vertices can G have?

- anonymous

Let G be a connected regular graph with n edges. How many vertices can G have?

- Stacey Warren - Expert brainly.com

Hey! We 've verified this expert answer for you, click below to unlock the details :)

- schrodinger

I got my questions answered at brainly.com in under 10 minutes. Go to brainly.com now for free help!

- anonymous

@TuringTest @amistre64 @satellite73

- Hero

n-1

- Hero

That's like the easiest graph question in the book

Looking for something else?

Not the answer you are looking for? Search for more explanations.

## More answers

- anonymous

Not true

- Hero

or n vertices

- anonymous

Here's a counter example:
|dw:1332548723247:dw|

- anonymous

4 vertices, 6 edges

- Hero

Oh, okay

- Hero

n(n-1)/2

- anonymous

hmm where did u get that from?

- Hero

From my head

- anonymous

No I need reasoning I don't just want the answer, any steps?

- Hero

Yeah, it's called trial and error

- Hero

Start with a graph of three edges, and then test using that. Then keep going until you find the pattern.

- anonymous

wait what's n? Number of edges?

- Hero

Yes

- anonymous

Then n(n-1)/2 doesn't work, the graph above has 6 edges, then according to u it must have:
6*5/2=15 vertices

- bahrom7893

@Zarkon

- Hero

I thought for sure the answer was one of those.

- bahrom7893

@KingGeorge

- Hero

@everybody

- anonymous

Hmm I'm not sure if amistre got a notification:
@amistre64

- anonymous

@JamesJ

- bahrom7893

@radar any ideas how to do this?

- amistre64

i got notifed but was buzy in a prior question

- radar

None. Was hoping someone had it.

- Hero

It can't be that difficult

- anonymous

oh yes it is lol this is graph theory

- Hero

I was just doing this not too long ago. It's not that difficult

- anonymous

It can get very nasty.. actually the original question asked:
Let G be a connected graph with 66 edges. How many vertices can G have?

- Hero

I apparently have forgotten the answer to the general question

- amistre64

Let G be a connected regular graph with n edges. How many vertices can G have?
vertices are the nodes, dots, point along the way?

- anonymous

Yea:
|dw:1332550157890:dw|
Those dots are vertices

- amistre64

and the edges are?

- anonymous

edges are the lines.. wait let me find what connected means, i forgot

- Hero

@mertsj

- amistre64

|dw:1332550278092:dw|
3 edges 4 verts; but i doubt this passes the connected definition

- anonymous

No i think connected means there's a vertex between any two edges.. but that could have meant complete, ughh too many definitions in graph theory.

- Hero

amistre, your graph isn't "connected". What you have posted is a "tree"

- bahrom7893

https://docs.google.com/viewer?a=v&q=cache:YbuM-CKfpCEJ:www.richardclegg.org/networks2/Lecture11_06.pdf+&hl=en&gl=us&pid=bl&srcid=ADGEESho_Z3gaZqZPI_kxMHzMa3zdVHP0KWn9VazgTJv0e-aiENRcJKxPh-26TR0TjiRhEsa54df2Etf8D2S4LrAsXr9hUF2Cy88pciUtxyooXcNWGweOdfbW8DexB-ceuANm5kn3RoY&sig=AHIEtbTbwt7Ll-UaIPaH8a58oFPXUdVU9w&pli=1

- radar

Use Hero's n(n-1)/2 where n is number of vertices (not edges)

- amistre64

http://mathworld.wolfram.com/RegularGraph.html
M=1/2 nr
where M = number of edges, n = number of nodes, and r = something regular :)

- bahrom7893

http://mathworld.wolfram.com/ConnectedGraph.html

- amistre64

trees are graphs i thought

- bahrom7893

There is a path between any two points, so amistre's tree is in fact connected, I can find a path between any two points.

- Mertsj

Every pair of vertices is connected by a unique edge.

- bahrom7893

Wait merts I think that's the definition of a complete graph

- bahrom7893

According to wolf:
http://mathworld.wolfram.com/ConnectedGraph.html
A graph which is connected in the sense of a topological space, i.e., there is a path from any point to any other point in the graph.

- Hero

What I meant to say was that the graph wasn't "complete" like bahrom said.

- Hero

I haven't dealt with graph theory in a while

- anonymous

argh

- amistre64

integrals a pirate lol

- anonymous

i got like all legends on my question.. lol

- Mertsj

Yes but we need Satellite

- Hero

I don't feel so bad now

- anonymous

I know, I reposted... I hate this class... crap.. just wanna swear so bad lol

- Hero

I told you to use trial and error

- anonymous

I think it's n+1

- Hero

Start with a complete graph of 3 vertices, then 4, then 5, and then keep going until you have a decent amount. You are bound to find the pattern

- anonymous

No, not complete, connected.

- Hero

Oh

- anonymous

|dw:1332551647588:dw|

- Mertsj

Do you have a list of answers from which to choose?

- anonymous

No lol and I have to write some reasoning for this.

- amistre64

3 edges can have at most 4 verts and at least 3 verts

- Hero

I finally found it. A tree with n vertices, has exactly n - 1 edges. So it looks like you were right.

- amistre64

6es can have at least 4 verts, and at most 7 verts

- Hero

So integral found the answer to his own question and mertsj gave the visual presentation. and like I said, It was easy. I just couldn't produce the results quickly enough. I hate graph theory as much as you do integral.

- Hero

Good luck with your reasoning

- anonymous

Wait the key point was regular.. Regular means each vertex has the same number of edges coming out of it. So the answer must be n

- anonymous

|dw:1332552193909:dw|

- Hero

Don't tell me you're going back to the very first answer I supplied

- Hero

well one of them at least

- anonymous

dude random guesses don't work here lol, I gotta prove this now

- Hero

Yes, it is important to specify whether you're dealing with a tree, a regular, or a complete graph.

- Hero

Maybe that would explain my "randomness"

- anonymous

Maybe reading the question would help? I specified that G was a connected regular graph lol

- Hero

I skipped right over the word "regular" Didn't even see it. My apologies

- Hero

I tend to do that sometimes.

- Hero

Here's what I thought I was reading the first time :
"Let G be a connected graph with n edges. How many vertices can G have?"
I feel that the confusion was all my fault.

Looking for something else?

Not the answer you are looking for? Search for more explanations.