Basic Graph Theory

by utkarshgupta, Mar 23, 2015, 4:42 PM

Problem :
All the vertices of a graph have degree $3$ . Proof that the graph has a cycle.

Solution 1 :
Consider any connected subgraph of this graph.
Since a tree has at least one vertex with degree $1$ , the given subgraph has a cycle.

Solution 2 :
Since a tree, always has a vertex with degree $1$ , if we show that the graph is connected, we are done.
Consider a vertex $X$ which is connected to vertices $A_i$ and not connected to $B_j$
If some $B_l$ is connected to some $A_m$ , we will have $B_l$ connected to $X$ a contradiction.

Thus we have $B_j$ and $X \cup A_i$ are disjoint subgraphs.

Thus by the induction hypothesis, we are done.

Comment

U VIEW ATTACHMENTS T PREVIEW J CLOSE PREVIEW rREFRESH

1 Comment

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Err, so I was going through your blog...

Are you sure that all graphs with minimum degree $\geq 3$ are connected? Or maybe you meant something else? Because I don't think that's true

For example, consider two disjoint complete graphs each of size 4.

Also, any graph with minimum degree $>1$ has a cycle. The condition that the graph is 3-regular is way too strong, isn't it?

by AnonymousBunny, May 8, 2015, 9:27 PM

Report

Submit

Here goes first post of 2025! Great blog.
by math_holmes15, Jan 14, 2025, 8:53 AM
First post of 2024
by Yiyj1, Feb 8, 2024, 5:40 AM
First post of 2023
by HoRI_DA_GRe8, Jul 22, 2023, 7:45 AM
Nice blog ! Your isogonality lemma is really powerful !
by 554183, Oct 14, 2021, 8:55 AM
Post plss....
by samrocksnature, Apr 11, 2021, 10:12 PM
alas,this is ded
by Hamroldt, Mar 18, 2021, 4:13 PM
Thanks for the nice blog.
by Feridimo, Mar 6, 2020, 4:17 PM
I think this might be silly but ... when should we expect to have another post ?? I am very keen to see it
by gamerrk1004, Nov 4, 2019, 4:54 PM
Let's all echo what's written in the blog description - Stay Insane / 'Cause it's your labor, will and pain/ That takes you to the top of soda fountain
by Kayak, Oct 2, 2017, 7:18 PM
hey utkarsh jee is over now ... continue your elementary blog pleaseeeeeee!
by kk108, Jun 17, 2017, 11:19 AM
Congrats on becoming a contest moderator!
by Ankoganit, Mar 9, 2017, 5:22 AM
INTERSTING BLOG
by kk108, Feb 19, 2017, 2:04 PM
I have no plans for this blog right now....
No time here people !
But lets see....
I may try some combinatorics
by utkarshgupta, Feb 15, 2017, 12:47 PM
Thanks for the nice blog!
by Orkhan-Ashraf_2002, Feb 13, 2017, 6:34 PM
Revive it!!!
Best blog out there, for sure!
by rmtf1111, Jan 12, 2017, 6:02 PM
Oh you certainly will..
Bu I don't think I will
by achilles04, Feb 11, 2015, 6:24 PM
Thanks
Hope you are there too ...

And hope I get selected
by utkarshgupta, Feb 11, 2015, 11:14 AM
Nice blog ..
keep it up and you might one day become a mathematician lIke me
( just joking )
Btw don't forget us after going to imotc.
by achilles04, Feb 10, 2015, 4:49 PM
nice blog!!!!!
by pradhit, Feb 7, 2015, 11:51 AM
No ideas about the cut off but should be less than 60 according to me...
So you never know
by utkarshgupta, Feb 6, 2015, 4:06 PM
Hi utkarsh,
what do u expect the cutoff to be this year??

by kgdpsdurg, Feb 6, 2015, 12:41 PM
Hi utkarsh
How many did you clear in INMO 2015?
by moldevort, Feb 1, 2015, 3:59 PM
@ Anonymous Bunny
If we both (that should have included me) are lucky enough !
by utkarshgupta, Sep 17, 2014, 2:44 AM
Nice blog. Great job!

If I am lucky enough, hopefully we shall meet at IMOTC.
by AnonymousBunny, Sep 16, 2014, 8:08 PM
Thanx all !!

If anyone wish to contribute anything just pm !

I will add u to the contributors' list !
by utkarshgupta, Sep 16, 2014, 6:35 AM
doing good progress!! btw nice blog.
by rachitgoel, Sep 15, 2014, 4:21 PM
Nice blog.
by Kezer, Aug 5, 2014, 4:04 PM
Hi Utkarsh! Wonderful blog. Keep it up.
by YESMAths, Jul 20, 2014, 1:36 PM
I need some shouts and characters

by utkarshgupta, Jul 20, 2014, 4:22 AM

48 shouts

Elementary

Basic Graph Theory

by utkarshgupta, Mar 23, 2015, 4:42 PM

1 Comment