Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

0
votes
2answers
8 views

Why does list coloring provides a more general setting to discuss the chromatic number?

I'm reading the Handbook of Graph Theory. It says the following: And a little before, the definitions of Chromatic Number: I don't understand what is this generality. Why the list ...
4
votes
0answers
30 views

Outline for high school combinatorics class?

I am a high school student and I have taken all the math classes that my school provides (through calculus AB). I have been looking at a possible independent study for next year and I have landed on ...
1
vote
0answers
7 views

Expected size of largest weakly connected component?

Given an undirected graph of n vertices and n randomly assigned edges, one edge from each vertex, what is the expected size of the largest connected component? For example, with four vertices, there ...
3
votes
2answers
36 views

Finite groups and topological spaces

Can we connect topological spaces with groups as: For topological space $X$ take biective homomorfisms $\phi: X\to X$, then divide such homomorphisms on classes of equivalency $\phi_1 \equiv\phi_2$ ...
2
votes
2answers
22 views

Matching Algorithm in Graph Theory

Given $n$ people, $k$ out of which own a car. We need to match a car for each person without a car. Conditions: Each car fits $5$ people, including the driver. Each driver will only allow his ...
0
votes
0answers
22 views

Are there any programs like family echo that I can use to map mathematics?

Family echo is an online program that allows one to make a family tree, if nothing is clicked it shows most of the family tree as it is, but if one clicks a name one can see clearly all the ancestors ...
0
votes
1answer
23 views

Factor of a Graph

Is $K_{2n}$ $2$-factorable? Illustrate with an example. $K_4$ is $2$-factorable but at many places it is generalized that $K_{2n}$ is not $2$-factorable. Is saying that a $2$-factor exists in a ...
-1
votes
0answers
21 views

Min. color $N$ if every $4$ vertex subgraph has a $3$ degree vertex [duplicate]

If a graph has $N$ vertices and every $4$ vertex subgraph has a $3$ degree vertex then prove there is a vertex with degree $N-1$.
2
votes
1answer
22 views

What is this binding function?

I'm reading the Handbook of Graph Theory. What is binding function (I mean, what function is it? $2x?$ $2x+x^2?$)? It says that it's a function $f:\mathbb{N}\to\mathbb{N}$ and it might have ...
2
votes
0answers
22 views

Check if graphs are Eulerian

I've been checking whether these graphs are Eulerian; I've come to conclusion that all of them are Eulerian, because they're all connected and all the vertices are of even degree. However, when I ...
3
votes
0answers
45 views

Combinatorics project ideas for high school students

It's that time again! Last year I asked for high school project ideas in the area of algebraic geometry, this year it's combinatorics (you can include graph theory and combinatorial game theory if you ...
2
votes
1answer
30 views

$3$-edge coloring of Georges Graph

Accoring to Wolfram|Alpha, Georges Graph $\hskip1in$ is 3-edge colorable. Does anybody have a actual 3-edge coloring in form of three sub-matrices of the adjacence matrix: $$A_1+A_2+A_3=A $$ I ...
1
vote
1answer
13 views

Proof by induction that for a complete simple and undirected graph that $|E|=\frac {n(n-1)} 2$

Prove with induction that for a complete simple and undirected graph that $|E|=\frac {n(n-1)} 2$ Base case is trivial. Suppose that for a graph with $n-1$ vertices we have $|E|=\frac ...
4
votes
0answers
22 views

Hamiltonian cycle and Euler Cycle. [duplicate]

When $G = K_n, n \ge 3$ and $n$ is odd, then from the edges of the $G$ can be built edge-disjoint Hamiltonian cycles. Is it true?
0
votes
1answer
17 views

Network/graph theory -acyclic problem [on hold]

Consider an acyclic directed network of n vertices, labeled $i=1...n$, and suppose that the labels are assigned such that all edges run from vertices with higher labels to vertices with lower. Show ...
0
votes
0answers
33 views

The triangle inequality for shortest paths of graphs

In why-the-triangle-inequality I found the statement: for example if $d(a,b)$ measures the "length" of the "shortest path" between points $a$ and $b$ (and this can be interpreted quite ...
0
votes
1answer
27 views

Prove: if the complementary graph is connected, then graph isn't necessarily unconnected.

I have such a question. There is a theorem related to graphs that says, that if a graph is disconnected then it's complementary graph is connected. But how can I prove that the inverse is not true, ...
0
votes
0answers
17 views

Symbol Identification related to set-theory and graph theory

If $A$ is a set of vertices of a graph $G$ where $A=\{V_1, V_2, V_3,V_4... V_N\}$, then what is the meaning of symbol $|A|$ ? I encountered this problem when I was reading a paper related to directed ...
2
votes
1answer
25 views

What is a graph isomorphism?

I am trying to under isomorphism in graphs, and from what I know, if graph A is isomorphic to graph B, then you could basically just rearrange the nodes in A, while keeping the edges connected the ...
0
votes
1answer
17 views

Is these Trees isomorphic or not?

Is these Trees isomorphic or not? They have same structure but they have different code. Because one of them is minimum code. Thank you for your answers in advance.
1
vote
1answer
43 views

Discrete math - Prove that a tree with n nodes must have exactly n - 1 edges? [duplicate]

I'm new in discrete math. Can someone prove simply that a tree with $n$ nodes must have exactly $n - 1$ edges. I have researched the solution but I haven't founded yet. I know of course, a tree with n ...
2
votes
0answers
38 views
+50

Quotient Groups and Covering Spaces in Painting Hanging

Consider the $1$-out-of-$n$ painting hanging problem: Given $n$ nails in a wall, how can we hang a painting such that upon removal of any nail, it falls. This has a nice interpretation as a problem in ...
0
votes
0answers
19 views
0
votes
0answers
46 views

What is the name of a graph structure with 'ports'?

I am wondering what the name of the following structure is. I might call it the madeup name "graph with ports" but most likely it already has a name that i am not aware of. The interesting thing to me ...
1
vote
1answer
13 views

Why can a set of edges of a bipartite graph with maximum degree d be partitioned in d matchings ?

In Wikipedia I read this: 'If there is a perfect matching, then both the matching number and the edge cover number are |V| / 2.' http://en.wikipedia.org/wiki/Matching_%28graph_theory%29 Is this the ...
2
votes
0answers
53 views

Is a “network topology'” a topological space?

Is there any connection between the computer science phrase "network topology" and the mathematical notion of a topological space (or, is there any other way to connect "network topologies" with ...
2
votes
0answers
26 views

Graphs with bounded degree: how many are there?

Can one count the number of undirected (simple) graphs on $n$ nodes with degree at most $d$? Asymptotic bounds would be helpful too.
0
votes
0answers
22 views

How many cases can draw diagonals that Applicable 2 above condition?

Imagine A $n$_regular polygon that vertex is named by $1$ to $n$. We know can draw $\frac{(n)(n+3)}{2}$ diagonals in $n$_regular polygon and also know if we want draw Maximum diagonals are not ...
0
votes
3answers
13 views

Proving if $G$ has no cycles but by adding one edge between any two vertices will create a cycle then $G$ is a tree

Prove: if $G$ has no cycles but by adding one edge between any two vertices it will create a cycle then $G$ is a tree. Below is the definition we use for a tree. I don't see any way to connect ...
1
vote
0answers
29 views

Expected size of largest connected component in a random k-out digraph?

Given a digraph with n vertices and kn edges, where each vertex has k out-neighbors randomly chosen at uniform without loops, how would I go about figuring out the expected value of the size of the ...
2
votes
1answer
21 views

Height of quasi-complete binary tree

Let us define a quasi-complete binary tree as a rooted binary whose nodes have all two children except at most those of the penultimate level, which can have either one or two children. I read that ...
0
votes
1answer
28 views

Let $G$ be a connected graph, then $G$ is a tree iff $G$ has no cycles

Prove the following: Let $G$ be a connected graph, then $G$ is a tree $\iff$ $G$ has no cycles. $\Rightarrow$ If $G$ is connected and a tree then by the definition of tree it has no cycles. ...
2
votes
0answers
29 views

A question about group actions on a trees [on hold]

why does the following conclusion hold: Let G be a group acting on a tree $\Gamma$, H a subgroup of G with minimal subtree $\Gamma_H$ and $g\in G$ be a hyperbolic element, s.t. $\langle g\rangle\cap ...
2
votes
1answer
22 views

Given a graph on $n$ vertices find the maximum amount of edges so it can be colored with no monochromatic $K_m$

I invented a problem and I wanted to share :What is the maximum amount of edges a graph on $n$ vertices can have if it can be edge-colored with $k$ colors so that it does not have a monochromatic ...
0
votes
1answer
22 views

Confusion about Hajós construction?

I've read this article on the Hajós construction. I've tried to execute it in a small graph to see it's results, I guess it would be something like this: These are the incidency matrices of $G,H$ and ...
0
votes
1answer
28 views

Average degree of $k$-degenerate graph is $\leq 2k$

How to prove the following claim? Average degree of $k$-degenerate graph is $\leq 2k$ Definition: Graph is $k$-degenerate if for every $\,G' = (V',E') \subset G$ there exists $v \in V'$ such ...
0
votes
2answers
38 views

Graph Theory Paths

Prove that every graph $G$ with $|G| < \|G\|$ contains a P$_{4}$. (P$_{4}$ is path with length $3$, $|G|$ is the number of vertices and $\|G\|$ is the number of edges). Would induction be the ...
1
vote
1answer
28 views

Without use the theorem that state $cr(C_3 \times C_t)=t$ for $t \geq 3$, show that $2 \leq cr(C_3 \times C_3) \leq 3$

Without use the theorem that state $cr(C_3 \times C_t)=t$ for $t \geq 3$, show that $2 \leq cr(C_3 \times C_3) \leq 3$ Here is what I got This is the graph of $C_3\times C_3$. It doen't matter how ...
2
votes
1answer
22 views

Graph with fixed amount of spanning trees

"Find a graph with 8 vertices, which have exactly 27 spanning trees." How do I find such a graph, or prove one does not exist?
1
vote
0answers
33 views

Infinite connected graph such that every vertex has finite degree

Let $G=(V,E)$ be an connected graph with $|V| \geq \aleph_0$ such that $\text{deg}(v)$ is finite for all $v\in V$. Does this imply that $|V|=\aleph_0$?
0
votes
1answer
21 views

About last part of proof of Brooks' theorem in a course in combinatorics

I am reading the proof of Theorem 3.1, which is Brooks' Theorem. I cannot understand the last part of the proof, which is on p.26 (link at google book). I don't understand what is $C_{ij}'$. I ...
1
vote
0answers
10 views

Generalizing interval graphs to higher dimensions

Not every graph is an interval graph, and that makes the notion of interval graph non-trivial. I was wondering whether the following generalization of interval ...
0
votes
1answer
17 views

Use theorem 6.23 to prove that the size of every outer planar graph of order $n \geq 2$ is at most $2n-3$

Use theorem 6.23 to prove that the size of every outer planar graph of order $n \geq 2$ is at most $2n-3$ Theorem 6.23: graph $G$ is outer planar if and only if $G \vee K_1$ is planar ...
1
vote
0answers
34 views

Let there be a connected graph $H$ and $p \in \mathbb N$. When are there $p$ spanning trees so that every edge is in at least one spanning tree?

Let there be a connected graph $H$ and $p \in \mathbb N$. When are there $p$ spanning trees so that every edge is in at least one spanning tree? What is the condition that needs to be met in order ...
6
votes
2answers
433 views

Is there a planar graph that (almost) all its vertices have degree 6?

Is it true that for any $N_0\in\mathbb N$ there exists a planar graph $G=(V,E)$ on (at least) $N_0$ vertices such that at least $$|V|(1-o(1))$$ vertices has degree 6? It is easy to show that no ...
3
votes
1answer
47 views

How to find a directed graph has a $d$ length walk between each pair of vertices?

$G=(V,E)$ where $|V|=n$ The outdegree and indegree of each vertice is set to 2. It may contains self-loops. Let $d=\lceil\log_2(n)\rceil$. Start with any vertice, we hope to reach all vertices ...
1
vote
1answer
19 views

If edges of $G$ are two colored, then there is a vertex of $G$ with at most two col0or changes in the cyclic order of the edges around the vertex.

Hello there i am reading proofs from the book of Gunter M ziegler. The chapter is called Three applications of eulers formula. Know there is a proposition which i don't fully understand and help would ...
0
votes
1answer
24 views

largest independent set in a circuit of length $n$

largest independent set in a circuit of length $7$ and $n$? For $7$, I guessed it's $3$. Guidance on finding for $n$?
0
votes
0answers
7 views

$k$-ary labeled trees with distinct labels

Classical definition of $k$-ary labeled trees doesn't restrict somehow the uniqueness of tree labels inside its branches. My question: Is any special definition (name) for such trees? To clarify ...
3
votes
1answer
32 views

Every graph can be optimally colored greedily.

I was at a conference today and someone said that if the graph $G$ has chromatic number $n$ then there is a way to order the vertices so that coloring greedily gives us a coloring with $n$ colors. By ...