Reputation
475
Top tag
Next privilege 500 Rep.
Access review queues
Badges
6 19
Impact
~23k people reached

  • 0 posts edited
  • 0 helpful flags
  • 25 votes cast
May
23
accepted Proving a simple graph is a connected graph
May
23
accepted Proofs involving subtrees of a tree
May
23
accepted Constructing a 3-regular graph with no 3-cycles
May
23
accepted Counting the number of graphs with a certain property
May
23
accepted How to show a graph is not Hamiltonian?
Apr
10
comment Counting the number of graphs with a certain property
I found something in the text that says if a graph has an odd cycle, then $\chi (G) \geq 3$. But how do I check all simple graphs with odd cycles to see which follow the property above?
Apr
10
asked Counting the number of graphs with a certain property
Apr
3
comment How to show a graph is not Hamiltonian?
Thank you very much for the clear answer! I am curious. Does a proof exist that does not require referencing the Petersen graph? (Even if it is the only graph satisfying such requirements) That is, is there some general criteria that would force a graph to be non-Hamiltonian based solely on the number of vertices/girth/regularness?
Apr
3
comment How to show a graph is not Hamiltonian?
$v_G$ is the number of vertices of $G$. I have edited my post to add this explanation!
Apr
3
revised How to show a graph is not Hamiltonian?
added 45 characters in body
Apr
3
comment How to show a graph is not Hamiltonian?
Oops, upon reading my post again I realize I forgot to add the property that $G$ was 3-regular. My bad! But nice counterexample for the original post.
Apr
3
revised How to show a graph is not Hamiltonian?
added 24 characters in body
Apr
3
asked How to show a graph is not Hamiltonian?
Mar
20
comment Proofs involving subtrees of a tree
Sorry, I didn't notice the typo. Indeed it was a nonempty intersection, and I've corrected the post.
Mar
20
revised Proofs involving subtrees of a tree
added 3 characters in body
Mar
20
asked Proofs involving subtrees of a tree
Mar
13
asked Proving a simple graph is a connected graph
Mar
13
comment Constructing a 3-regular graph with no 3-cycles
No, there cannot, but I'm having trouble writing this "formally". Do I simply write that this is because $k+1$, say, would only have edges between $k$, $k+2$, and $k+(n+1)$, and so $k+n$ is not included?
Mar
13
revised Constructing a 3-regular graph with no 3-cycles
added 1 characters in body
Mar
13
comment Constructing a 3-regular graph with no 3-cycles
Oops, yes, my bad!