Reputation
22,581
Next tag badge:
351/400 score
96/80 answers
Badges
4 18 61
Newest
 Nice Answer
Impact
~390k people reached

1d
comment bound on vertices of graph with path
@BorisMorozov Perhaps there is some mundane solution, but I am not aware of it. On the other hand, although this is a rather hard problem, it is not impossible to find such a proof (perhaps not as streamlined, but working). Also, that could have been one of the remember-from-class questions, who knows?
1d
answered Prove a graph $(V,E)$ with $d$-maximal degree let $k=d/2+1$ can be decomposed as $V=V_1 \cup\cdots \cup V_k$ where each $V_i$ is a loopless graph
1d
comment bound on vertices of graph with path
@BorisMorozov Sure, for example you can start with your assumption, and then arrive at my last line which is clearly a contradiction, but what for? Proofs by contradiction are, in a sense, weaker than direct proofs.
1d
comment Representing all pairs shortest path in a graph with a matrix
There may be expotentially many such paths, so your only option is some compact representation. Perhaps the length of the shortest path between any pair of vertices will be enought for you?
1d
comment What does $M_{uv}^l$ represent?
Think of a weighted graph, for example you can start with one where each edge has length $10$.
Jul
27
comment Is there a profitable way to read mathematical proofs
I doubt you would want, in most cases, to go through the whole process the author(s) underwent to arrive at the result. On the other hand, in an ideal world the proofs would be accompanied by a foreword that describes the relevant intuitions, why's, whynot's, etc. In particular, some of the best research papers I have read were that good because of the intuitions, explanations and methods they provided, not because of the dry results contained within.
Jul
27
comment Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes
If $f$ can be an arbitrary function, then it is not even in $\mathsf{NP}$, in particular to prove that some subgraph $G'$ is indeed the global minimum you have to enumerate all the graphs with desired properties. (And I assume that by real value you mean some approximation like double, because true real values are quite hard to deal with by themselves).
Jul
27
comment Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?
I was hoping that Haxify would solve this problem by himself/herself too, and I think that your hints are great, so it is worth to preserve them. What I had in mind would take too long to describe in a comment, so I've taken the liberty to just edit your answer. Please rollback or edit further if it does not suit you in any way.
Jul
27
revised Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?
Hint+spoilers based on OP's comments.
Jul
27
comment Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?
@Batominovski You could make your comments an answer.
Jul
27
comment what are these kind of graphs called in graph theory ?
Could you give us some context, for example, where this question comes from?
Jul
26
comment Directed Acyclic Graph - root and leaf node terminology
What @Marconius said, I have frequently seen source and sink used in this context. Although, don't forget to define it, just to be clear.
Jul
24
comment Property of maximum matching
You have constructively found the vertex $v$ and maximum matchings $M_e \ni e$ for any edge $e$ incident to $v$. Why do you need the contradiction, this proof would be much better without it.
Jul
24
comment Graphically representing relations of ordered pairs
Two rational numbers $\frac{a}{b}$ and $\frac{c}{d}$ (of course $b \neq 0 \neq d$) are equal if and only iff $ad=bc$.
Jul
23
comment Size of a maximum matching of a complete multipartite graph?
@user111691 And what is the size of the matching in the second case?
Jul
23
comment Size of a maximum matching of a complete multipartite graph?
@user111691 The indices start at $0$, so the last one is $n-1$, not $n$, and the last of the first half is $\frac{n}{2}-1$, because $\frac{n}{2}$ is the first index of the second half. For example let $n=6$, then the first half is $\{0,1,2\}$, while the second is $\{3,4,5\}$ and we would like $0\leq i \leq 2 < 3=\frac{6}{2}$ so that for $i=2$ we have $i+\frac{n}{2} = 2+3 \leq n-1=5 < n = 6$.
Jul
23
revised Size of a maximum matching of a complete multipartite graph?
added 150 characters in body
Jul
23
answered Size of a maximum matching of a complete multipartite graph?
Jul
17
comment Prove that the following program terminates
See Collatz conjecture.
Jul
17
comment Most natural intro to Complex Numbers
How to Fold a Julia Fractal contains quite intuitive intro to complex numbers. It's certainly not enough, but I would start in a similar fashion.