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

-5
votes
0answers
27 views

Example of graph pebbling number and significance

According to the Wikipedia article on graph pebbling: Graph pebbling is a mathematical game and area of interest played on a graph with pebbles on the vertices. 'Game play' is composed of a ...
0
votes
0answers
25 views

What is $\langle I\rangle$ in this text?

I've read the following: It is easy to see that given any independent set $I$ in $V$, the vertices of $V-I$ form a covering of $G$. Conversely, if $V-I$ forms a covering, then $\langle I\rangle$ ...
1
vote
1answer
21 views

All the combination of cycles of consecutive numbers

Let say that we have $N$ consecutive number $1,2,...,N$ and we want to find all the possible consecutive number cycles of length $2n+1$. For example: $$\begin{align}&N = 5\\&n = 3\ \ \ \ ...
0
votes
1answer
16 views

Randomized Algorithm for finding perfect matchings

I'm stuck on some of the theory in these notes, i'm trying to learn about randomized algorithms in general and am currently stuck on some notes regarding perfect matchings. Here is a link to the ...
2
votes
1answer
13 views

Relation between number of tree edges in graph with $n$ vertices and $k$ components.

It's a sort of given in my book without any proof that : $$t=n-k$$ where, $t$ = the number of tree edges $n$ = number of vertices $k$ = number of components. Can someone explain me the ...
5
votes
1answer
49 views

Almost every graph is asymmetric?

Here is a question: If i choose at random an isomorphism class of graph(no loops, undirected) on n vertices(with uniform probability on the set of such isomorphism classes), is the probability that ...
1
vote
1answer
22 views

Nearest neighbour algorithm (or so I think).

The algorithm is as follows: Given a graph, we start with some arbitrary vertex, in this vertex the path starts. From a vertex we are at we proceed to a neighbour vertex along some edge, we're keeping ...
1
vote
0answers
7 views

Show that a comparability graph is perfect.

Show that a comparability graph is perfect. I'm trying to be able to prove Dilworth's Theorem from perfect graphs. I'll cite the perfect graph theorem for the complement step. This is the part ...
2
votes
1answer
24 views

Adding an edge and a vertex to non-isomorphic graphs

Let $G$ and $H$ be two non-isomorphic simple graphs of equal order and equal size. Suppose I am to add a vertex $v$ and and edge $e$ incident to $v$ to $G$ and $H$. By add I mean to connect $v$ to ...
1
vote
2answers
24 views

Complement of a bipartite graph

What constraint must be placed on a bipartite graph G to guarantee that G's complement will also be bipartite? I see someone saying that it can't be 4 or more in each group, but I don't see why. I ...
2
votes
1answer
28 views

Network Theorem

Our Electrical Engineering professor told us about this formula relating to circuits: $$Network \ Theorem: \ \ \ \ b = m+n-1$$ where $b$ = number of branches in circuit, $m$ = number of closed ...
0
votes
0answers
24 views

Clique cycles structure

I am currently going through the paper "Covering two-edge-coloured complete graphs with two disjoint monochromatic cycles" by Peter Allen (http://www.ime.usp.br/~allen/twocycle.pdf) and I have some ...
2
votes
1answer
19 views

Difference of two graphs

Given two graphs $G_{1}$ and $G_{2}$ what exactly is the definition of $G_{1}-G_{2}$ used in the Diestel book? Most operations on graphs are clearly defined apart from this one.
0
votes
1answer
13 views

Spectral gap vs. algebraic connectivity

Can someone please clarify how the spectral gap of a graph relates to its algebraic connectivity (aka Fiedler value) and whether these use the adjacency matrix or laplacian matrix?
0
votes
0answers
7 views
0
votes
1answer
18 views

How many undirected graphs are possible with $4$ labelled vertices such that exactly $1$ edge is present?

I have drawn the graph and the result is $6$ graphs are possible. A simple graph can have a maximum of $\Large\binom{n}{2}$ edges and each edge can exist or not exist. Therefore, ...
2
votes
1answer
28 views

Chromatic number and vertex covering number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$. Let $\chi(G)$ denote the chromatic number of $G$. Is there a graph $G$ with $\tau(G) < \chi(G) - 1$?
0
votes
2answers
32 views

Discrete maths proving a random observation

Suppose you had 6 points. Each point can choose to either visit another point, or choose not to visit another point. However, it can't visit itself. In addition, visiting another point works in both ...
0
votes
0answers
22 views

Reference for the proof of interlacing of eigenvalues of submatrices

If one has a $n \times n$ Hermitian matrix $A$ and one removes $k$ of the rows and their corresponding columns then the eigenvalues of the remnant interlace the eigenvalues of the full matrix. Can ...
0
votes
0answers
13 views

How do I find point locations on a graph from edges and one known point position?

I have been given a collection of nodes and edges such that each node connects to every other node by an edge. All the edge lengths are known. One of the nodes locations (x,y) is known, but the rest ...
0
votes
2answers
18 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
3answers
67 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
29 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
61 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
26 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 ...
1
vote
0answers
25 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
27 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
23 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
24 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
52 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
19 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
38 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
29 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
18 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
27 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
18 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 ...
4
votes
0answers
60 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
23 views
1
vote
0answers
47 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
14 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
57 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
27 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
34 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 ...